比赛 |
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;
}