记录编号	435334	评测结果	AAAAAAAAAA
题目名称	[USACO Jan14]奶牛冰壶运动	最终得分	100
用户昵称	wumingshi	是否通过	通过
代码语言	C++	运行时间	0.143 s
提交时间	2017-08-09 16:55:43	内存使用	1.81 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=50005;
struct point
{
	int x,y;
	point(){}
	point(int xx,int yy):x(xx),y(yy){}
	inline point operator -(const point other)const
	{
		return point(x-other.x,y-other.y);
	}
	inline bool operator <(const point other)const
	{
		if(x==other.x) return y<other.y;
		return x<other.x;
	}
}a1[N],a2[N],s1[N],s2[N];
int n,top1,top2,ans1,ans2;
inline ll cross(point a,point b)
{
	return 1ll*a.x*b.y-1ll*b.x*a.y;
}
inline ll supercross(point a,point b,point c)
{
	return cross(b-a,c-b);
}
inline bool onleft(point a,point b,point c)
{
	return supercross(a,b,c)>0;
}
inline void solve(point *a,point *s,int &top)
{
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++)
	{
		while(top>1&&cross(s[top]-s[top-1],a[i]-s[top-1])<=0) top--;
		s[++top]=a[i];
	}
	int num=top;
	for(int i=n-1;i;i--)
	{
		while(top>num&&cross(s[top]-s[top-1],a[i]-s[top-1])<=0) top--;
		s[++top]=a[i];
	}
}
inline bool check(point a,point b,point p)
{
	if(a.y==b.y) return 0;
	if((a.y<p.y&&p.y<=b.y&&!onleft(a,b,p))||(b.y<p.y&&p.y<=a.y&&!onleft(b,a,p))) return 1;
	return 0;
}
inline int getans(point *s,int top,point *a)
{
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		int num=0;
		for(int j=1;j<top;j++)
		  if(check(s[j],s[j+1],a[i])) num++;
		if(num&1) ans++;
	}
	return ans;
}
int main()
{
	freopen("curling.in","r",stdin);
	freopen("curling.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	  scanf("%d%d",&a1[i].x,&a1[i].y);
	for(int i=1;i<=n;i++)
	  scanf("%d%d",&a2[i].x,&a2[i].y);
	solve(a1,s1,top1),solve(a2,s2,top2);
	ans1=getans(s1,top1,a2),ans2=getans(s2,top2,a1);
	if(!ans1&&!ans2) return printf("4 4"),0;
	printf("%d %d",ans1,ans2);
	return 0;
}