比赛 20140418 评测结果 AWWWWWWWWW
题目名称 奶牛冰壶运动 最终得分 10
用户昵称 Miku_lyt 运行时间 0.187 s
代码语言 C++ 内存使用 1.46 MiB
提交时间 2014-04-18 10:41:30
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>

using namespace std;

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

int dist(point x,point y){
  return (x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.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){
  for (int i=1;i<=top;i++){
    if (ang(x,t[s[i]],t[s[i+1]])<0){
      return 0;
      }
    }
  return 1;
  }

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||(ang(t[s[top-1]],t[s[top]],t[i])==0&&dist(t[s[top-1]],t[s[top]])<=dist(t[s[top-1]],t[i])))){
      top--;
      }
    top++;
    s[top]=i;
    }
  s[top+1]=s[1];

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

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

  scanf("%d",&n);
  for (int i=1;i<=n;i++){
    scanf("%d%d",&t[i].x,&t[i].y);
    }
  for (int i=1;i<=n;i++){
    scanf("%d%d",&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;
  }