记录编号	202484	评测结果	AAAATTTTTA
题目名称	[SYOI 2015] Asm_Def的模拟赛	最终得分	50
用户昵称	前鬼后鬼的守护	是否通过	未通过
代码语言	C++	运行时间	10.072 s
提交时间	2015-11-01 12:07:20	内存使用	0.30 MiB

#include<cstdio>
#include<algorithm>
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}
int n,x[400],y[400],ans,sum;
inline int outmul(int s,int t1,int t2){
	int x1=x[t1]-x[s],y1=y[t1]-y[s],x2=x[t2]-x[s],y2=y[t2]-y[s];
	return y1*x2-y2*x1;
}
inline bool consist(int x,int y,int z,int p){
	return (outmul(x,y,p)>=0&&outmul(y,z,p)>=0&&outmul(z,x,p)>=0)||
			(outmul(x,y,p)<=0&&outmul(y,z,p)<=0&&outmul(z,x,p)<=0);
}
void check(int x,int y,int z){
	int o=3;
	for(int p=1;p<=n;p++)if(p!=x&&p!=y&&p!=z)
		if(consist(x,y,z,p))
			o++;
	if(o>ans)ans=o,sum=1;
	else if(o==ans)sum++;
}
int line[400],tot,prev[400],next[400];
int que[400],head,tail,size;
int s,t;
inline int inmul(int s,int t1,int t2){
	int x1=x[t1]-x[s],y1=y[t1]-y[s],x2=x[t2]-x[s],y2=y[t2]-y[s];
	return x1*x2+y1*y2;
}
inline bool mycmp(int a,int b){
	return inmul(s,t,a)<inmul(s,t,b);
}
inline void remove(int k){
	next[prev[k]]=next[k];
	prev[next[k]]=prev[k];
}
void work(){
	std::sort(line+1,line+1+tot,mycmp);size=0;
	for(int i=1;i<=tot+1;i++)prev[i]=i-1;
	for(int i=0;i<=tot;i++)next[i]=i+1;
	for(int x=1;x<=tot;x=next[x])
		while(next[x]<=tot&&consist(s,line[x],t,line[next[x]]))
			que[++size]=line[next[x]],remove(next[x]);
	for(int x=tot;x;x=prev[x])
		while(prev[x]>0&&consist(s,line[x],t,line[prev[x]]))
			que[++size]=line[prev[x]],remove(prev[x]);
	std::sort(que+1,que+1+size,mycmp);head=1,tail=0;if(size==0)return;
	for(int x=next[0];x<=tot;x=next[x]){
		while(head<=tail&&!consist(s,line[x],t,que[head]))
			head++;
		while(tail+1<=size&&consist(s,line[x],t,que[tail+1]))
			tail++;
		int temp=tail-head+4;
		if(temp>ans)ans=temp,sum=1;
		else if(temp==ans)sum++;
	}
}
void check(){
	tot=0;for(int i=1;i<=n;i++)if(i!=s&&i!=t&&outmul(s,t,i)<=0)line[++tot]=i;work();
	tot=0;for(int i=1;i<=n;i++)if(i!=s&&i!=t&&outmul(s,t,i)>=0)line[++tot]=i;work();
}
int main(){
	freopen("trib.in","r",stdin);
	freopen("trib.out","w",stdout);
	n=read();for(int i=1;i<=n;i++)x[i]=read(),y[i]=read();
	ans=3,sum=n*(n-1)*(n-2)/6;
	if(n<=100){
		for(int i=1;i<=n;i++)
			for(int j=i+1;j<=n;j++)
				for(int k=j+1;k<=n;k++)
					check(i,j,k);
		printf("%d\n%d",ans,sum);
	}	
	else {
		for(s=1;s<=n;s++)
			for(t=s+1;t<=n;t++)
				check();
		printf("%d\n%d",ans,sum/3);
	}
	return 0;
}