记录编号	98097	评测结果	AWWWWWWWWW
题目名称	[USACO Jan14]奶牛冰壶运动	最终得分	10
用户昵称	digital-T	是否通过	未通过
代码语言	C++	运行时间	0.206 s
提交时间	2014-04-21 17:55:34	内存使用	0.31 MiB

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<fstream>
#include<complex>
#include<vector>
#include<deque>
using namespace std;
int N;
struct Point
{
	double x,y;
	Point(double x=0,double y=0):x(x),y(y){};
};
typedef Point Vector;
Vector operator + (Vector A,Vector B){return Vector(A.x+B.x,A.y+B.y);}//向量加减
Vector operator - (Point A,Point B){return Vector(A.x-B.x,A.y-B.y);}
Vector operator * (Vector A,double p){return Vector(A.x*p,A.y*p);}//向量与数量乘除
Vector operator / (Vector A,double p){return Vector(A.x/p,A.y/p);}
bool operator < (const Point& a,const Point& b){return a.x<b.x||(a.x==b.x&&a.y<b.y);}//排序用
const double eps=1e-10;
int dcmp(double x){if(fabs(x)<eps)return 0;else return x<0?-1:1;}
bool operator ==(const Point& a,const Point &b){return dcmp(a.x-b.x)==0 && dcmp(a.y-b.y)==0;}//精度问题上的 判断相同
double Dot(Vector A,Vector B){return A.x*B.x+A.y*B.y;}//点积
double Length(Vector A){return sqrt(Dot(A,A));}//向量的模
double Angle(Vector A,Vector B){return acos(Dot(A,B)/Length(A)/Length(B));}//向量的夹角
double Cross(Vector A,Vector B){return A.x*B.y-A.y*B.x;}//叉积
double Area2(Point A,Point B,Point C){return Cross(B-A,C-A);}//三角形面积
Vector Rotate(Vector A,double rad){return Vector(A.x * cos(rad) - A.y * sin(rad) , A.x * sin(rad) + A.y * cos(rad));}//向量旋转rad角度
Vector Normal(Vector A){double L=Length(A);return Vector(-A.y/L,A.x/L);}//调用前确保A不是零向量
/*
//复数  #include<complex>
typedef complex<double> Point;
typedef Point Vector;
double Dot(Vector A,Vector B){return real(conj(A)*B);}//点积
double Cross(Vector A,Vector B){return imag(conj(A)*B);}//叉积
Vector Rotate(Vector A,double rad){return A*exp(Point(0,rad));}//旋转
//复数
*/
Point GetLineIntersection(Point P,Vector v,Point Q,Vector w)//直线的交点，必须保证有唯一交点
{
	Vector u=P-Q;
	double t=Cross(w,u)/Cross(v,w);
	return P+v*t;
}
double DistanceToLine(Point P,Point A,Point B)//点到直线的距离
{
	Vector v1=B-A,v2=P-A;
	return fabs(Cross(v1,v2)/Length(v1));//如果不取绝对值则得到是有向距离
}
double DistanceToSegment(Point P,Point A,Point B)//点到线段的距离
{
	if(A==B)return Length(P-A);
	Vector v1=B-A,v2=P-A,v3=P-B;
	if(dcmp(Dot(v1,v2))<0)return Length(v2);
	else if(dcmp(Dot(v1,v3))>0)return Length(v3);
	else return fabs(Cross(v1,v2))/Length(v1);
}
Point GetLineProjection(Point P,Point A,Point B)//点在直线上的距离
{
	Vector v=B-A;
	return A+v*(Dot(v,P-A)/Dot(v,v));
}
bool SegmentProperIntersection(Point a1,Point a2,Point b1,Point b2)//线段相交判定
{
	double c1=Cross(a2-a1,b1-a1),c2=Cross(a2-a1,b2-a1),c3=Cross(b2-b1,a1-b1),c4=Cross(b2-b1,a2-b1);
	return dcmp(c1)*dcmp(c2)<0 && dcmp(c3)*dcmp(c4)<0;
}
bool OnSegment(Point p,Point a1,Point a2){	return dcmp(Cross(a1-p,a2-p))==0 && dcmp(Dot(a1-p,a2-p))<0;}//判断一个点是否在一条线段上
vector <Point> pA,pB,ansA,ansB;
void ConvexHull(vector<Point> &p,int n,vector<Point> &ch)//水平序
{
	sort(p.begin(),p.end());
	for(int i=0;i<n;i++)
	{
		while(ch.size()>1 && Cross(ch[ch.size()-1]-ch[ch.size()-2],p[i]-ch[ch.size()-2])<0)ch.pop_back();
		ch.push_back(p[i]);
	}
	int k=ch.size();
	for(int i=n-2;i>=0;i--)
	{
		while(ch.size()>k && Cross(ch[ch.size()-1]-ch[ch.size()-2],p[i]-ch[ch.size()-2])<0)ch.pop_back();
		ch.push_back(p[i]);
	}
	if(n>1)ch.pop_back();
	return;
}
int find(Point x,int l,int r,vector <Point> &hull)
{
	if(l==r)return l;
	int mid=(l+r)>>1;
	if(Cross(hull[mid]-hull[0],x-hull[0])>0)return find(x,l,mid,hull);
	else return find(x,mid+1,r,hull);
}
bool inside(Point x,vector <Point> &hull)
{
	if(Cross(hull[1]-x,hull[0]-x)>0)return 0;
	if(Cross(hull[0]-x,hull.back()-x)>0)return 0;
	int k=find(x,0,hull.size()-2,hull);
	if(Cross(hull[k+1]-x,hull[k+2]-x)<0)return 0;
	return 1;
}
void work(vector <Point> &A,vector <Point> &B)//A的得分
{
	int ans=0;
	for(int i=0;i<N;i++)
		ans+=inside(B[i],A);
	printf("%d ",ans);
}
int main()
{
	freopen("curling.in","r",stdin);
	freopen("curling.out","w",stdout);
	scanf("%d",&N);
	double x,y;
	for(int i=0;i<N;i++)
	{
		scanf("%lf%lf",&x,&y);
		pA.push_back(Point(x,y));
	}
	for(int i=0;i<N;i++)
	{
		scanf("%lf%lf",&x,&y);
		pB.push_back(Point(x,y));
	}
	ConvexHull(pA,N,ansA);
	ConvexHull(pB,N,ansB);
	/*for(int i=0;i<ansA.size();i++)
		printf("%.2lf %.2lf\n",ansA[i].x,ansA[i].y);
	for(int i=0;i<ansB.size();i++)
		printf("%.2lf %.2lf\n",ansB[i].x,ansB[i].y);*/
	work(ansA,pB);
	work(ansB,pA);
	return 0;
}