记录编号	97320	评测结果	AAAAAAAAAA
题目名称	[USACO Jan14]奶牛冰壶运动	最终得分	100
用户昵称	◆半城烟沙灬為你打天下	是否通过	通过
代码语言	C++	运行时间	0.228 s
提交时间	2014-04-18 14:48:25	内存使用	1.46 MiB

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<iostream>
using namespace std;
struct sky
{
	int x,y;
};
int head,tail,n;
sky a[50000],b[50000],q[50000];
long long s,s2;
bool comp(sky a,sky b)
{
	return a.y<b.y ||(a.y==b.y&&a.x<b.x);
}
long long CJ(sky a,sky b,sky c)
{
	long long x1=b.x-a.x,y1=b.y-a.y,x2=c.x-a.x,y2=c.y-a.y;
	return x1*y2-x2*y1;
}
long long abc(long long a)
{
	return a<0?-a:a;
}
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",&a[i].x,&a[i].y);
	}
	for (int i=1;i<=n;i++)
	{
		scanf("%d%d",&b[i].x,&b[i].y);
	}
	sort(a+1,a+n+1,comp);
	sort(b+1,b+n+1,comp);
	head=tail=1;
	q[1]=a[1];
	for (int i=2;i<=n;i++)
	{
		while ( (tail-head)>0 &&CJ(q[tail-1],q[tail],a[i])<=0) tail--;
		q[++tail]=a[i];
	}
	head=tail;
	for (int i=n-1;i;i--)
	{
		while ( (tail-head)>0 &&CJ(q[tail-1],q[tail],a[i])<=0) tail--;
		q[++tail]=a[i];
	}
	tail--;
	s=0;
	for (int i=2;i<=tail;i++)
	{
		s+=CJ(q[1],q[i],q[i+1]);
	}
	int ans=0;
	for (int i=1;i<=n;i++)
	{
		if (s!=0)
		{
			s2=0;
			for (int j=1;j<tail;j++)
			{
				s2+=abc(CJ(b[i],q[j],q[j+1]));
			}	
			s2+=abc(CJ(b[i],q[tail],q[1]));
			if (s2==s) ans++;
		}
		else
		{
			if (b[i].x>=min(q[1].x,q[tail].x) && b[i].x<=max(q[1].x,q[tail].x) && b[i].y>=min(q[1].y,q[tail].y) && b[i].y<=max(q[1].y,q[tail].y))
			{
				ans++; 
			}
		}
	}
	printf("%d ",ans);
	head=tail=1;
	q[1]=b[1];
	for (int i=2;i<=n;i++)
	{
		while ( (tail-head)>0 &&CJ(q[tail-1],q[tail],b[i])<=0) tail--;
		q[++tail]=b[i];
	}
	head=tail;
	for (int i=n-1;i;i--)
	{
		while ( (tail-head)>0 &&CJ(q[tail-1],q[tail],b[i])<=0) tail--;
		q[++tail]=b[i];
	}
	s=0;
	tail--;
	for (int i=2;i<=tail;i++)
	{
		s+=CJ(q[1],q[i],q[i+1]);
	}
	ans=0;
	for (int i=1;i<=n;i++)
	{
		if (s!=0)
		{
			s2=0;
			for (int j=1;j<tail;j++)
			{
				s2+=abc(CJ(a[i],q[j],q[j+1]));
			}
			s2+=abc(CJ(a[i],q[tail],q[1]));
			if (s2==s) ans++;
		}
		else
		{
			if (a[i].x>=min(q[1].x,q[tail].x) && a[i].x<=max(q[1].x,q[tail].x) && a[i].y>=min(q[1].y,q[tail].y) && a[i].y<=max(q[1].y,q[tail].y))
			{
				ans++; 
			}
		}
	}
	printf("%d",ans);
}