比赛 20140418 评测结果 WWWWWEEWEW
题目名称 奶牛冰壶运动 最终得分 0
用户昵称 GDFRWMY 运行时间 0.428 s
代码语言 C++ 内存使用 2.26 MiB
提交时间 2014-04-18 09:34:32
显示代码纯文本
#include<fstream>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>

#define inf 100000000
#define zero 1e-5
using namespace std;
ifstream fin("curling.in");
ofstream fout("curling.out");
int n;
typedef struct{double x,y,tan; int g;}node;
node a[51000];
int xx[51000],yy[51000];
int s[51000],t=0,ans;
 double minx=inf,miny=inf;

bool cmp(node a,node b)
{
    return a.tan<b.tan;
}


inline double cross(double x1,double y1,double x2,double y2)
{
    return x1*y2-x2*y1;
}


inline void init()
{
   
   fin>>n;
	n=2*n;
	for (int i=1; i<=n; ++i){
	fin>>xx[i]>>yy[i];
	}
    for (int i=1; i<=n; ++i)
        {
			a[i].x=xx[i];
			a[i].y=yy[i];
			if (i<=n/2)
				a[i].g=1;
			else
				a[i].g=0;
            if (a[i].x<minx)
                {
                    minx=a[i].x;
                    miny=a[i].y;
                }
        }
		 
    for (int i=1; i<=n; ++i)
        {
            a[i].x-=minx; a[i].y-=miny;
	
            if ((a[i].x==0) && (a[i].y==0)) 
                {
                    swap(a[1],a[i]);
                    continue;
                }
            if (a[i].x==0) a[i].x=zero;
            a[i].tan=a[i].y/a[i].x;
        }
    sort(a+2,a+n+1,cmp);
}



inline void init2()
{
    minx=inf;miny=inf;
    for (int i=1; i<=n/2; ++i)
        {
			a[i].x=xx[i+n/2];
			a[i].y=yy[i+n/2];
			a[i].g=1;
            if (a[i].x<minx)
                {
                    minx=a[i].x;
                    miny=a[i].y;
                }
        }
    for (int i=n/2+1; i<=n; ++i)
        {
			a[i].x=xx[i-n/2];
			a[i].y=yy[i-n/2];
			a[i].g=0;
            if (a[i].x<minx)
                {
                    minx=a[i].x;
                    miny=a[i].y;
                }
        }	
    for (int i=1; i<=n; ++i)
        {
            a[i].x-=minx; a[i].y-=miny;
            if ((a[i].x==0) && (a[i].y==0)) 
                {
                    swap(a[1],a[i]);
                    continue;
                }
            if (a[i].x==0) a[i].x=zero;
            a[i].tan=a[i].y/a[i].x;
        }
    sort(a+2,a+n+1,cmp);
}


inline void push(int x)
{

    while ((t>1) && (cross(a[x].x-a[s[t]].x,a[x].y-a[s[t]].y,a[s[t-1]].x-a[s[t]].x,a[s[t-1]].y-a[s[t]].y)<=0)){
		if (a[x].g==0){ ans++;	 return;}
		else
        t--;
	}
	if (a[x].g==1)    s[++t]=x;
		//fout<<a[x].x+minx<<' '<<a[x].y+miny<<' '<<a[x].g<<' '<<t<<endl;
}

inline void work()
{
    for (int i=1; i<=n; ++i)
        push(i);
    fout<<n/2-ans<<endl;
}



void clear(){
	ans=0;
	t=0;
	memset(s,0,sizeof(s));
}
  
int main()
{
 
    init();
	
    work();
	clear();init2();work();
    return 0;
}