记录编号	97369	评测结果	AAAAAAAAAA
题目名称	[USACO Jan14]奶牛冰壶运动	最终得分	100
用户昵称	FF_Sky||幻	是否通过	通过
代码语言	C++	运行时间	0.308 s
提交时间	2014-04-18 18:16:36	内存使用	17.45 MiB

#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;

struct arr{
	ll x,y;
}a[500001],b[500001];

int ans1,ans2,n,p,s[500001];
ll temp;

bool com(const arr &a,const arr &b){
	if (a.y < b.y) return 1;
	if (a.y == b.y && a.x < b.x) return 1;
	return 0;
}

ll muil(arr _1,arr _2,arr _3){
	return ((_2.x-_1.x)*(_3.y-_1.y)-(_3.x-_1.x)*(_2.y-_1.y));
}

bool judge1(arr _){
	ll tem = 0;
	for (int i = 1; i < p; i++){
		tem += abs(muil(_,a[s[i]],a[s[i+1]]));
	}
	tem += abs(muil(_,a[s[p]],a[s[1]]));
	return (tem == temp && temp > 0) || (temp == 0 && tem == 0 && _.x >= a[1].x && _.x <= a[n].x && _.y >= a[1].y && _.y <= a[n].y);
}

bool judge2(arr _){
	ll tem = 0;
	for (int i = 1; i < p; i++){
		tem += abs(muil(_,b[s[i]],b[s[i+1]]));
	}
	tem += abs(muil(_,b[s[p]],b[s[1]]));
	return (tem == temp && temp > 0) || (tem == 0 && temp == 0 && _.x >= b[1].x && _.x <= b[n].x && _.y >= b[1].y && _.y <= b[n].y);
}

int main(){
	freopen("curling.in","r",stdin);
	freopen("curling.out","w",stdout);
	int i;
	scanf("%d",&n);
	for (i = 1; i <= n; i++) scanf("%lld%lld",&a[i].x,&a[i].y);
	for (i = 1; i <= n; i++) scanf("%lld%lld",&b[i].x,&b[i].y);
	sort(a+1,a+n+1,com);
	s[1] = 1; s[2] = 2; p =2;
	for (i = 3; i <= n; i++){
		while (muil(a[s[p-1]],a[s[p]],a[i]) <= 0 && p > 1) p--;
		s[++p] = i;
	}
	s[++p] = n-1;
	for (i = n-2; i > 0; i--){
		while (muil(a[s[p-1]],a[s[p]],a[i]) <= 0 && p > 1) p--;
		s[++p] = i;
	}
	p--;
	for (i = 1; i < p; i++){
		temp += muil(a[0],a[s[i]],a[s[i+1]]);
	}
	temp -= muil(a[0],a[s[1]],a[s[p]]);
	for (i = 1; i <= n; i++){
		if (judge1(b[i])) ans1++;
	}
	temp = 0;
	sort(b+1,b+n+1,com);
	s[1] = 1; s[2] = 2; p =2;
	for (i = 3; i <= n; i++){
		while (muil(b[s[p-1]],b[s[p]],b[i]) <= 0 && p > 1) p--;
		s[++p] = i;
	}
	s[++p] = n-1;
	for (i = n-2; i > 0; i--){
		while (muil(b[s[p-1]],b[s[p]],b[i]) <= 0 && p > 1) p--;
		s[++p] = i;
	}
	p--;
	for (i = 1; i < p; i++){
		temp += muil(b[0],b[s[i]],b[s[i+1]]);
	}
	temp -= muil(b[0],b[s[1]],b[s[p]]);
	for (i = 1; i <= n; i++){
		if (judge2(a[i])) ans2++;
	}
	printf("%d %d\n",ans1,ans2);
}