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

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

using namespace std;

struct point{
  long long x,y;
  };
  
  point t[50050],t2[50050],t3[50050];
  int s[50050];
  int n;
  int ans1,ans2;
  int tot=0;
  int top=0;
  long long area=0;
  
long long abss(long long x){
  if (x>=0){
    return x;
    }
  return -x;
  }
  
long long ang(point a,point b,point c){
  return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
  }

long long dist(point a,point b){
  return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
  }

bool cmp(const point x,const point y){
  if (ang(t[1],x,y)<0){
    return 0;
    }
  else{
    if (ang(t[1],x,y)>0){
      return 1;
      }
    else{
      return dist(t[1],x)<dist(t[1],y);
      }
    }
  }
  
bool have(point x){
  long long area1=0;
  for (int i=1;i<=top;i++){
    area1+=abss(ang(x,t[s[i]],t[s[i+1]]));
    }
  if (area==area1){
    return 1;
    }
  return 0;
  }

void make(){
  memset(s,0,sizeof(s));
  int now=0;
  int xx=0x3f3f3f3f;
  int yy=0x3f3f3f3f;
  for (int i=1;i<=n;i++){
    if (t[i].x<xx){
      xx=t[i].x;
      yy=t[i].y;
      now=i;
      }
    else{
      if (t[i].x==xx&&t[i].y<yy){
        yy=t[i].y;
        now=i;
        }
      }
    }
  t[0]=t[1];
  t[1]=t[now];
  t[now]=t[0];
  sort(t+2,t+n+1,cmp);
  top=2;
  s[1]=1;
  s[2]=2;
  for (int i=3;i<=n;i++){
    while (top>1&&ang(t[s[top-1]],t[s[top]],t[i])<0){
      top--;
      }
    top++;
    s[top]=i;
    }
  s[top+1]=s[1];

  area=0;
  for (int i=1;i<=top;i++){
    area+=abss(ang(t[1],t[s[i]],t[s[i+1]]));
    }

  tot=0;
  for (int i=1;i<=n;i++){
    if (have(t2[i])){
      tot++;
      }
    }
  if (area==0){
    tot--;
    }
  }

int main(){
  freopen("curling.in","r",stdin);
  freopen("curling.out","w",stdout);

  scanf("%d",&n);
  for (int i=1;i<=n;i++){
    scanf("%lld%lld",&t[i].x,&t[i].y);
    }
  for (int i=1;i<=n;i++){
    scanf("%lld%lld",&t2[i].x,&t2[i].y);
    }

  make();
  ans1=tot;
  memcpy(t3,t,sizeof(t3));
  memcpy(t,t2,sizeof(t));
  memcpy(t2,t3,sizeof(t2));

  make();
  ans2=tot;

  printf("%d %d\n",ans1,ans2);

  return 0;
  }