比赛 Asm_Def战记之透明计算网络 评测结果 AWAWWWAAWW
题目名称 Asm_Def的模拟赛 最终得分 40
用户昵称 debug 运行时间 0.045 s
代码语言 C++ 内存使用 0.29 MiB
提交时间 2015-11-01 11:51:51
显示代码纯文本
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
struct ff
{
	int x,y;
}f[333]={};
int n;
int maxx=-1;
int shuliang=0;
bool bunengyong[333]={};
double xielv[4]={};
int check2(int a,int b,int c,int d)
{
	int zuo=999999;
	zuo=min(f[a].x,zuo);
	zuo=min(f[b].x,zuo);
	zuo=min(f[c].x,zuo);
	if(zuo>f[d].x)//在左端的左边
		return 0;
	int you=-999999;
	you=max(f[a].x,you);
	you=max(f[b].x,you);
	you=max(f[c].x,you);
	if(you<f[d].x)//在右端的右边
		return 0;
	//下面计算斜率,可以看出,两点均在左端或右端不影响结果;
	if(xielv[0]>xielv[1])
		swap(xielv[0],xielv[1]);
	if(xielv[2]>xielv[3])
		swap(xielv[3],xielv[2]);
	double te=(1.0*f[d].y-f[a].y)/(1.0*f[d].x-f[a].x);
	if(!(te<=xielv[1]&&te>=xielv[0]))
		return 0;
	te=(1.0*f[c].y-f[d].y)/(1.0*f[c].x-f[d].x);
	if(!(te<=xielv[3]&&te>=xielv[2]))
		return 0;
	return 1;//左右条件均符合,即为在三角形内
}
void check(int a,int b,int c)
{
	if(f[a].x>f[b].x)
		swap(a,b);
	if(f[a].x>f[c].x)
		swap(a,c);
	if(f[b].x>f[c].x)
		swap(b,c);
	xielv[0]=(1.0*f[b].y-f[a].y)/(1.0*f[b].x-f[a].x);
	xielv[1]=xielv[2]=(1.0*f[c].y-f[a].y)/(1.0*f[c].x-f[a].x);
	xielv[3]=(1.0*f[c].y-f[b].y)/(1.0*f[c].x-f[b].x);
	xielv[0]-=0.00000000001;
	xielv[1]+=0.00000000001;
	xielv[2]-=0.00000000001;
	xielv[3]+=0.00000000001;
	int temp=0;
	for(int i=1;i<=n;i++)
		if(i==a||i==b||i==c)
			continue;
		else if(check2(a,b,c,i)==1)
			temp++,bunengyong[i]=1;
	if(temp>maxx)
		maxx=temp,shuliang=1;
	else if(temp==maxx)
		shuliang++;
}
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",&f[i].x,&f[i].y);
	for(int i=1;i<=n-2;i++)
	{
		if(bunengyong[i])
			continue;
		for(int j=i+1;j<=n-1;j++)
		{
			if(bunengyong[j])
				continue;
			for(int k=j+1;k<=n;k++)
			{
				if(bunengyong[k])
					continue;
				check(i,j,k);
			}
		}
	}
	printf("%d\n%d\n",maxx+3,shuliang);
}