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

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<list>
#include<deque>
using namespace std;
typedef long long ll;
const ll SIZEN=50010;
ll N;
class POINT{
public:
	ll x,y;
	void print(void){
		cout<<"("<<x<<","<<y<<")";
	}
};
POINT operator - (POINT a,POINT b){
	return (POINT){a.x-b.x,a.y-b.y};
}
bool operator < (POINT a,POINT b){//靠下为小,然后靠左为小
	if(a.y==b.y) return a.x<b.x;
	return a.y<b.y;
}
ll crp(POINT a,POINT b){
	//x1y2-x2y1
	//如果为正表明b在a的逆时针
	return a.x*b.y-a.y*b.x;
}
void swap(POINT &a,POINT &b){
	POINT c;
	c=a;a=b;b=c;
}
bool anticlock(POINT x,POINT a,POINT b){//以x为视点,b是否在a的逆时针
	return crp(a-x,b-x)>0;
}
ll cross(POINT a,POINT b,POINT c){
	return crp(b-a,c-a);
}
ll sgn(ll x){
	if(x==0) return 0;
	if(x<0) return -1;
	if(x>0) return 1;
}
bool comp(POINT a,POINT b){
	return a.x<b.x||sgn(a.x-b.x)==0&&a.y<b.y;
}
deque<POINT> H;
ll s[SIZEN]={0};
void quickhull(POINT p[SIZEN],ll l,ll r,POINT a,POINT b){
	ll x=l,i=l-1,j=r+1,k;
	for(k=l;k<=r;k++){
		ll temp=sgn(s[x]-s[k]);
		if(temp<0||temp==0&&comp(p[x],p[k])) x=k;
	}
	POINT y=p[x];
	for(k=l;k<=r;k++){
		s[++i]=cross(p[k],a,y);
		if(sgn(s[i])>0) swap(p[i],p[k]);
		else i--;
	}
	for(k=r;k>=l;k--){
		s[--j]=cross(p[k],y,b);
		if(sgn(s[j])>0) swap(p[j],p[k]);
		else j++;
	}
	if(l<=i) quickhull(p,l,i,a,y);
	H.push_back(y);
	if(j<=r) quickhull(p,j,r,y,b);
}
deque<POINT> hull;
void inverse(void){
	ll x=1,y=hull.size()-1;
	while(x<y){
		swap(hull[x],hull[y]);
		x++,y--;
	}
}
void gethull(POINT p[SIZEN]){//好像叫快速凸包算法什么的
	H.clear();
	hull.clear();
	memset(s,0,sizeof(s));
	ll x=0;
	for(ll i=1;i<=N;i++){
		if(x==0||comp(p[i],p[x])) x=i;
	}
	swap(p[1],p[x]);
	H.push_back(p[1]);
	quickhull(p,2,N,p[1],p[1]);
	x=0;
	for(ll i=1;i<H.size();i++){
		if(H[i]<H[x]) x=i;
	}
	for(ll i=x;i<H.size();i++) hull.push_back(H[i]);
	for(ll i=0;i<x;i++) hull.push_back(H[i]);
	if(!anticlock(hull[0],hull[1],hull[2])) inverse();
}
ll find(POINT x,ll left,ll right){
	if(left==right) return left;
	ll mid=(left+right)/2;
	if(anticlock(hull[0],x,hull[mid+1])) return find(x,left,mid);
	else return find(x,mid+1,right);
}
ll inside(POINT x){
	if(anticlock(hull[0],x,hull[1])) return 0;
	if(anticlock(hull[0],hull.back(),x)) return 0;
	ll k=find(x,0,hull.size()-2);
	if(anticlock(hull[k],x,hull[k+1])) return 0;
	if(hull.size()==2){
		if(sgn(x.x-hull[0].x)*sgn(x.x-hull[1].x)==1) return 0;
		if(sgn(x.y-hull[0].y)*sgn(x.y-hull[1].y)==1) return 0;
	}
	return 1;
}
ll enclose(POINT pa[SIZEN],POINT pb[SIZEN]){
	gethull(pa);
	ll ans=0;
	for(ll i=1;i<=N;i++) ans+=inside(pb[i]);
	return ans;
}
POINT P1[SIZEN],P2[SIZEN];
void read(void){
	scanf("%lld",&N);
	for(ll i=1;i<=N;i++) scanf("%lld%lld",&P1[i].x,&P1[i].y);
	for(ll i=1;i<=N;i++) scanf("%lld%lld",&P2[i].x,&P2[i].y);
}
int main(){
	freopen("curling.in","r",stdin);
	freopen("curling.out","w",stdout);
	read();
	printf("%lld ",enclose(P1,P2));
	printf("%lld\n",enclose(P2,P1));
	return 0;
}