记录编号	97355	评测结果	AAAAAAAAAA
题目名称	[USACO Jan14]奶牛冰壶运动	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.196 s
提交时间	2014-04-18 17:03:02	内存使用	1.84 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;
}
ll sgn(ll x){
	if(x>0) return 1;
	if(x==0) return 0;
	return -1;
}
ll cross(POINT x,POINT a,POINT b){//向量xa与向量xb的叉积
	return crp(a-x,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;
}
void Graham(vector<POINT> &hull,POINT p[SIZEN]){
	vector<int> st1,st2;
	sort(p+1,p+1+N);
	st1.push_back(1);st1.push_back(2);
	bool visit[SIZEN]={0};
	for(int i=3;i<=N;i++){//右链,共线的应尽量取靠后的点
		int tot=st1.size()-1;
		while(st1.size()>=2&&cross(p[st1[tot-1]],p[i],p[st1[tot]])>=0){
			st1.pop_back();
			tot--;
		}
		st1.push_back(i);
	}
	for(int i=0;i<st1.size();i++) visit[st1[i]]=true;
	st2.push_back(N);st2.push_back(N-1);
	for(int i=N-2;i>=1;i--){//左链,共线的应尽量取靠前的点
		int tot=st2.size()-1;
		while(st2.size()>=2&&cross(p[st2[tot-1]],p[i],p[st2[tot]])>=0){
			st2.pop_back();
			tot--;
		}
		st2.push_back(i);
	}
	hull.clear();
	for(int i=0;i<st1.size();i++) hull.push_back(p[st1[i]]);
	for(int i=1;i<st2.size();i++) if(!visit[st2[i]]) hull.push_back(p[st2[i]]);
}
vector<POINT> hull;
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]){
	hull.clear();
	Graham(hull,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;
}