比赛 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;
}