比赛 |
Asm_Def战记之透明计算网络 |
评测结果 |
AAAATTTTTA |
题目名称 |
Asm_Def的模拟赛 |
最终得分 |
50 |
用户昵称 |
Fmuckss |
运行时间 |
10.118 s |
代码语言 |
C++ |
内存使用 |
27.46 MiB |
提交时间 |
2015-11-01 11:57:02 |
显示代码纯文本
- #include<stdio.h>
- #include<iostream>
- #include<algorithm>
- #include<cmath>
- #define maxn 305
- #define inf 1005
- using namespace std;
- bool use[maxn][maxn],use2[maxn][maxn][maxn];
- struct node{
- int x,y;
- bool edg;
- bool chos;
- }ns[maxn];
- int n,amax,ans;
- bool cmp(node a,node b){
- return a.y==b.y ? a.x<b.x:a.y<b.y;
- }
- void read(){
- scanf("%d",&n);
- for(int i=1;i<=n;i++){
- scanf("%d %d",&ns[i].x,&ns[i].y);
- use[n][n]=true;
- }
- sort(ns+1,ns+n+1,cmp);
- for(int i=1;i<=n;i++){
- int tmpx=ns[i].x,tmpy=1;
- while(tmpx==ns[i].x){
- if(tmpy){
- ns[i].edg=true;
- tmpy=0;
- i++;
- continue;
- }
- ns[i].edg=false;
- i++;
- }
- i--;
- ns[i].edg=true;
- }
- }
- int s(int x1,int y1,int x2,int y2,int x3,int y3){
- return abs(x1*y2+y1*x3+x2*y3-y2*x3-y1*x2-y3*x1);
- }
- void solve(){
- for(int i=1;i<=n;i++){
- if(!ns[i].edg) continue;
- int x1=ns[i].x,y1=ns[i].y;
- for(int j=1;j<=n;j++){
- if(use[i][j]||i==j||(!ns[j].edg))continue;
- int x2=ns[j].x,y2=ns[j].y;
- use[i][j]=true;use[j][i]=true;
- for(int k=1;k<=n;k++){
- if(use2[i][j][k])continue;
- if(k==i||k==j||(!ns[j].edg))continue;
- int x3=ns[k].x,y3=ns[k].y;
- int tot=0;
- for(int m=1;m<=n;m++){
- int x4=ns[m].x,y4=ns[m].y;
- int tmp1=s(x1,y1,x2,y2,x3,y3),
- tmp2=s(x1,y1,x2,y2,x4,y4),
- tmp3=s(x1,y1,x4,y4,x3,y3),
- tmp4=s(x4,y4,x2,y2,x3,y3);
- if(tmp1==tmp2+tmp3+tmp4){
- tot++;
- }
- }
- if(tot==amax){
- ans++;
- }else if(tot>amax){
- amax=tot;
- ans=1;
- }
- }
- }
- }
- }
- int main(){
- freopen("trib.in","r",stdin);
- freopen("trib.out","w",stdout);
- read();
- solve();
- printf("%d\n%d",amax,ans/3);
- return 0;
- }