比赛 Asm_Def战记之透明计算网络 评测结果 AAAAWWAAWA
题目名称 Asm_Def的模拟赛 最终得分 70
用户昵称 Satoshi 运行时间 0.176 s
代码语言 C++ 内存使用 0.32 MiB
提交时间 2015-11-01 09:32:25
显示代码纯文本
#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <iomanip>
#include <stack>
#define N 310
using namespace std;
ifstream in("trib.in");
ofstream out("trib.out");
int n;
vector<int> H;
stack<int> S;
bool vis[N]={0};
class point
{
public:
	int x;
	int y;
	double co;
	point operator +(const point a)
	{
		point b;
		b.x=x+a.x;
		b.y=y+a.y;
		return b;
	}
	point operator -(const point a)
	{
		point b;
		b.x=x-a.x;
		b.y=y-a.y;
		return b;
	}
	int operator *(const point a)
	{
		int solo;
		solo=x*a.x+y*a.y;
		return solo;
	}
	int operator ^(const point a)
	{
		int solo;
		solo=x*a.y-y*a.x;
		return solo;
	}
	void print()
	{
		out<<x<<' '<<y<<endl;
	}
}po[N],start,end;
bool com(point a,point b)
{
	if(a.y<b.y)return 1;
	if(a.y==b.y)
	{
		if(a.x<b.x)return 1;
	}
	return 0;
}
bool som(point a,point b)
{
	if(a.co>b.co)return 1;
	if(a.co==b.co)
	{
		if(a*a<b*b)return 1;
	}
	return 0;
}
void getHull()
{
	int i,af,bf;
	int s=0;
	point a,b;
	S.push(1);S.push(2);S.push(3);
	for(i=4;i<=n;i++)
	{
		while(true)
		{
		   af=S.top();S.pop();
		   bf=S.top();S.push(af);
		   a=po[af]-po[bf];
		   b=po[bf]-po[i];
		   s=a^b;
		   if(s>0)S.pop();
		   else break;
		}
		S.push(i);
	}
	while(!S.empty())
	{
		H.push_back(S.top());
		S.pop();
	}
}
bool check(int a,int b,int c,int d)//判断d是否在三角形A,B,C内
{
	int SA=0,SB=0,SC=0,SD;
	bool flag=0;
	point A,B,C,D,E,F;
	A=po[a]-po[d];B=po[b]-po[d];C=po[c]-po[d];
	SA=A^B;SB=B^C;SC=C^A;
	if(SA<=0&&SB<=0&&SC<=0)flag=1;
	if(SA>=0&&SB>=0&&SC>=0)flag=1;
	return flag;
}
void work()
{
	int i,j,k,l;
	int ans1=0,ans2=0,temp=0;
	int I,J,K,L;
	for(i=0;i<H.size();i++)
	{
		I=H[i];
		for(j=i+1;j<H.size();j++)
		{
			J=H[j];
			for(k=j+1;k<H.size();k++)
			{
				K=H[k];
				temp=0;
				//out<<H[i]<<' '<<H[j]<<' '<<H[k]<<endl;
				for(l=1;l<=n;l++)
				{
					if(l==I||l==J||l==K)continue;//重点
					if(vis[l])continue;//凸包上的点
					if(check(I,J,K,l))temp++;
				}
				if(temp>ans1)ans1=temp;
				//out<<temp<<endl;
			}
		}
	}
    for(i=0;i<H.size();i++)
	{
		I=H[i];
		for(j=i+1;j<H.size();j++)
		{
			J=H[j];
			for(k=j+1;k<H.size();k++)
			{
				K=H[k];
				temp=0;
				//out<<H[i]<<' '<<H[j]<<' '<<H[k]<<endl;
				for(l=1;l<=n;l++)
				{
					if(l==I||l==J||l==K)continue;//重点
					if(vis[l])continue;//凸包上的点
					if(check(I,J,K,l))temp++;
				}
				if(temp==ans1)ans2++;
			}
		}
	}
	ans1+=3;
	out<<ans1<<' '<<ans2<<endl;
}
void work2()
{
	int i,j,k,l;
	int ans1=0,ans2=0,temp=0;
	for(i=1;i<=n;i++)
	{
		for(j=i+1;j<=n;j++)
		{
			for(k=j+1;k<=n;k++)
			{
				temp=0;
				for(l=1;l<=n;l++)
				{
					if(l==i||l==j||l==k)continue;
					if(check(i,j,k,l))temp++;
				}
				if(temp>ans1)ans1=temp;
			}
		}
	}
	for(i=1;i<=n;i++)
	{
		for(j=i+1;j<=n;j++)
		{
			for(k=j+1;k<=n;k++)
			{
				temp=0;
				for(l=1;l<=n;l++)
				{
					if(l==i||l==j||l==k)continue;
					if(check(i,j,k,l))temp++;
				}
				if(temp==ans1)ans2++;
			}
		}
	}
	ans1+=3;
	out<<ans1<<' '<<ans2<<endl;
}
int main()
{
	int i,u;
	in>>n;
	for(i=1;i<=n;i++)in>>po[i].x>>po[i].y;
	sort(po+1,po+n+1,com);
	start=po[1];
	for(i=n;i>=1;i--)po[i]=po[i]-po[1];
	//for(i=1;i<=n;i++)po[i].print();
	for(i=1;i<=n;i++)
	{
		po[i].co=atan2(double(po[i].x),double(po[i].y));
		if(po[i].x==0&&po[i].y==0)po[i].co=9999;
	}
	sort(po+1,po+n+1,som);
	getHull();
	for(i=0;i<H.size();i++)vis[H[i]]=1;
	//out<<H.size()<<endl;
	/*for(i=0;i<H.size();i++)
	{
		u=H[i];
		out<<u<<' ';
		end = po[u] + start;
		end.print();
	}*/
	if(n>=100)work();
	else
	{
		work2();
	}
	return 0;
}