比赛 Asm_Def战记之透明计算网络 评测结果 WWWWTTTTTW
题目名称 Asm_Def的模拟赛 最终得分 0
用户昵称 FETS 1/3 运行时间 10.093 s
代码语言 C++ 内存使用 1.73 MiB
提交时间 2015-11-01 11:26:50
显示代码纯文本
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
const int maxn=305;
const double wc=0.000001;
int n;
struct pointt
{
	int x;
	int y;
};
pointt p[maxn];
int ans=0;
double k[maxn][maxn];
double B[maxn][maxn];
int main()
{
	freopen("trib.in","r",stdin);
	freopen("trib.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d %d",&p[i].x,&p[i].y);
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=i+1;j<=n;j++)
		{
			if(p[i].x==p[j].x)
			{
				k[i][j]=1005+p[i].x;
				B[i][j]=1005+p[i].x;
				continue;
			}
			if(p[i].y==p[j].y)
			{
				k[i][j]=0;
				B[i][j]=p[i].y;
				continue;
			}
			k[i][j]=double(double(p[j].y-p[i].y)/double(p[j].x-p[i].x));
			B[i][j]=p[j].y-k[i][j]*p[j].x;
		}
	}
	int maxx=-1;
	for(int a=1;a<=n;a++)
	{
		for(int b=a+1;b<=n;b++)
		{
			for(int c=b+1;c<=n;c++)
			{
				double k1=k[a][b];
				double k3=k[b][c];
				double k2=k[a][c];
				double b1=B[a][b];
				double b2=B[a][c];
				double b3=B[b][c];
				int te=0;
				for(int w=1;w<=n;w++)
				{
					int wx=p[w].x;
					int wy=p[w].y;
					if(fabs(wy-(k1*wx+b1))<=wc||fabs(wy-(k2*wx+b2))<=wc||fabs(wy-(k3*w+b3))<=wc||k1-1005==wx||k2-1005==wx||k3-1005==wx)
					{
						te++;
						continue;
					}
					else
					{
						double t1=wy-(k1*wx+b1);
						double t2=wy-(k2*wx+b2);
						double t3=wy-(k3*wx+b3);
						if(t1*(p[c].y-(k1*p[c].x+b1))>0&&t2*(p[b].y-(k2*p[b].x+b2))>0&&t3*(p[a].y-(k3*p[a].x+b3))>0)
							te++;
					}
				}
				if(te>maxx)
				{	
					maxx=max(maxx,te);
					ans=1;
					continue;
				}
				if(te==maxx)
					ans++;
			}
		}
	}
	printf("%d\n%d",maxx,ans);
}