记录编号	97298	评测结果	AAAAAAAAAA
题目名称	[USACO Jan14]奶牛冰壶运动	最终得分	100
用户昵称	LuciFer_T-J	是否通过	通过
代码语言	C++	运行时间	0.229 s
提交时间	2014-04-18 11:59:10	内存使用	11.76 MiB

#include<cstring>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>

using namespace std;
#define MAXN 500005
struct node{
	int x,y;
}a[MAXN],b[MAXN],q[MAXN];
int n,l,r,ans;
long long S,S2;

bool comp(node a,node b){
	return a.y < b.y || (a.y==b.y && a.x<b.x);
}

long long  CJ(node a,node b,node 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);
	int i,j;
	scanf("%d",&n);
	for (i=1;i<=n;i++){
		scanf("%d%d",&a[i].x,&a[i].y);
	}
	for (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);
	// work(A)
	l=r=1;
	q[1]=a[1];
	for (i=2;i<=n;i++){
		while (r-l>0 && CJ(q[r-1],q[r],a[i])<=0) r--;
		q[++r]=a[i];
	}
	l=r;
	for (i=n-1;i;i--){
		while (r-l>0 && CJ(q[r-1],q[r],a[i])<=0) r--;
		q[++r]=a[i];
	}
	r--;
	S=0;
	for (i=2;i<r;i++){
		S+=CJ(q[1],q[i],q[i+1]);
	}
	ans=0;
	for (i=1;i<=n;i++){
		if (S){			
			S2=0;
			for (j=1;j<r;j++){
				S2+=abc(CJ(b[i],q[j],q[j+1]));
			}
			S2+=abc(CJ(b[i],q[r],q[1]));
				if (S2==S) ans++;
		}
		else{
			if (b[i].x>=min(q[1].x,q[r].x) && b[i].x<=max(q[1].x,q[r].x) && b[i].y>=min(q[1].y,q[r].y) && b[i].y<=max(q[1].y,q[r].y)){
				ans++;
			}
		}
	}
	cout<<ans<<" ";
	//work(B)
	l=r=1;
	q[1]=b[1];
	for (i=2;i<=n;i++){
		while (r-l>0 && CJ(q[r-1],q[r],b[i])<=0) r--;
		q[++r]=b[i];
	}
	l=r;
	for (i=n-1;i;i--){
		while (r-l>0 && CJ(q[r-1],q[r],b[i])<=0) r--;
		q[++r]=b[i];
	}
	S=0;
	r--;
	for (i=2;i<r;i++){
		S+=CJ(q[1],q[i],q[i+1]);
	}
	ans=0;
	for (i=1;i<=n;i++){
		if (S){			
			S2=0;
			for (j=1;j<r;j++){
				S2+=abc(CJ(a[i],q[j],q[j+1]));
			}
			S2+=abc(CJ(a[i],q[r],q[1]));
				if (S2==S) ans++;
		}
		else{
			if (a[i].x>=min(q[1].x,q[r].x) && a[i].x<=max(q[1].x,q[r].x) && a[i].y>=min(q[1].y,q[r].y) && a[i].y<=max(q[1].y,q[r].y)){
				ans++;
			}
		}
	}
	cout<<ans<<endl;
}