| 记录编号 |
237381 |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
| 题目名称 |
[国家集训队2011]元素之泉 |
最终得分 |
100 |
| 用户昵称 |
 mikumikumi |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
0.260 s |
| 提交时间 |
2016-03-17 09:33:52 |
内存使用 |
23.35 MiB |
显示代码纯文本
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<deque>
#include<ctime>
using namespace std;
const int SIZEN=10010;
const double zero=1e-8;
int N,M;
double ys[SIZEN][6];
class miku
{
public:
double x,y,z;
int sum;
miku()
{
x=y=z=0;
sum=0;
}
void print()
{
cout<<x<<" "<<y<<" "<<z<<endl;
}
}P[SIZEN];
bool cmp1(miku a,miku b)
{
//if(abs(a.x-b.x)<zero&&abs(a.y-b.y)<zero) return a.z<b.z;
//else if(abs(a.x-b.x)<zero) return a.y<b.y;
return a.x<b.x;
}
bool cmp2(miku a,miku b)
{
if(abs(a.y-b.y)<zero) return a.x<b.x;
return a.y<b.y;
}
void read()
{
scanf("%d%d",&N,&M);
for(int i=1;i<=N;i++)
{
for(int j=1;j<=M;j++) scanf("%lf",&ys[i][j]);
}
}
void calc_0()//0维凸包
{
if(N==1) printf("0\n");
else printf("%d\n",N);
}
void calc_1()//1维凸包,所有的点都在x+y=100这条直线上
{
int ans=N-2;
for(int i=1;i<=N;i++) P[i].x=ys[i][1];
sort(P+1,P+1+N,cmp1);
//for(int i=1;i<=N;i++) cout<<P[i].x<<endl;
if(P[2].x-P[1].x<zero) ans++;
if(P[N].x-P[N-1].x<zero) ans++;
printf("%d\n",ans);
}
//***********case2***************//
miku operator - (miku a,miku b)
{
miku c;
c.x=a.x-b.x;c.y=a.y-b.y;c.z=a.z-b.z;
return c;
}
double operator * (miku a,miku b)
{
double re=0;
re=a.x*b.y-b.x*a.y;
return re;
}
double cross2(miku a,miku b,miku c)
{
miku tem1,tem2;
tem1=b-a;tem2=c-b;
double re=tem1*tem2;
return re;
}
void calc_2()//二维凸包，graham
{
for(int i=1;i<=N;i++){P[i].x=ys[i][1];P[i].y=ys[i][2];}
sort(P+1,P+1+N,cmp2);
deque<int> st1,st2;
st1.push_back(1);st1.push_back(2);
if(abs(P[2].x-P[1].x)<zero&&abs(P[2].y-P[1].y)<zero) P[1].sum++;
for(int i=3;i<=N;i++)
{
int tot=st1.size()-1;
if(abs(P[st1[tot]].x-P[i].x)<zero&&abs(P[st1[tot]].y-P[i].y)<zero) P[st1[tot]].sum++;
else while(tot>=1&&cross2(P[st1[tot-1]],P[st1[tot]],P[i])>=0) st1.pop_back(),tot--;
st1.push_back(i);
}
bool visit[SIZEN]={0};
for(int i=0;i<st1.size();i++) visit[st1[i]]=1;
st2.push_back(N);st2.push_back(N-1);
if(abs(P[N].x-P[N-1].x)<zero&&abs(P[N].y-P[N-1].y)<zero) P[N].sum++;
for(int i=N-2;i>=1;i--)
{
int tot=st2.size()-1;
if(abs(P[st2[tot]].x-P[i].x)<zero&&abs(P[st2[tot]].y-P[i].y)<zero) P[st2[tot]].sum++;
else while(tot>=1&&cross2(P[st2[tot-1]],P[st2[tot]],P[i])>=0) st2.pop_back(),tot--;
st2.push_back(i);
}
int ans=0;
for(int i=0;i<st1.size();i++) if(!P[st1[i]].sum) ans++;
for(int i=0;i<st2.size();i++) if(!P[st2[i]].sum&&!visit[st2[i]]) ans++;
ans=N-ans;
printf("%d",ans);
}
//****************case3*************//
class poi
{
public:
int x,y,z;
int del;
poi()
{
del=x=y=z=0;
}
}f[1111*1111];//面
int cnt=0;
int random(int x,int y)
{
return rand()%(y-x+1)+x;
}
miku cross3(miku a,miku b)//叉积
{
miku re;
re.x=a.y*b.z-a.z*b.y;re.y=a.z*b.x-b.z*a.x;re.z=a.x*b.y-a.y*b.x;
return re;
}
double det(miku a,miku b)//点积
{
return a.x*b.x+a.y*b.y+a.z*b.z;
}
bool outside(poi a,miku b)
{
miku tem=cross3(P[a.z]-P[a.y],P[a.y]-P[a.x]);
double t=det(tem,b-P[a.x]);
if(t>zero) return 1;
return 0;
}
int to[1111][1111];
void work(int a,int b);
void go(int a,int b,int c);
void go(int a,int b,int c)//判断含有b->a这条边的面是否保留
{
int tem=to[b][a];
if(f[tem].del) return;
if(outside(f[tem],P[c])) work(tem,c);
else
{
f[++cnt].x=a;f[cnt].y=b;f[cnt].z=c;
to[a][b]=to[b][c]=to[c][a]=cnt;
}
}
void work(int a,int b)//将平面a删去
{
if(f[a].del) return;
f[a].del=1;
go(f[a].x,f[a].y,b);
go(f[a].y,f[a].z,b);
go(f[a].z,f[a].x,b);
}
void calc_3()
{
srand(time(NULL));
for(int i=1;i<=N;i++)
{
for(int j=1;j<=M;j++) P[i-1].x=ys[i][1],P[i-1].y=ys[i][2],P[i-1].z=ys[i][3];
}
for(int i=0;i<N;i++) swap(P[i],P[random(i,N-1)]);
for(int i=0;i<4;i++)//我们先把前四个点变成一个四面题
{
int a=i,b=(i+1)&3,c=(i+2)&3;
f[++cnt].x=a;f[cnt].y=b;f[cnt].z=c;
if(outside(f[cnt],P[(c+1)&3]))
{
swap(a,b);
swap(f[cnt].x,f[cnt].y);
}
to[a][b]=to[b][c]=to[c][a]=cnt;//顺时针标记
}
for(int i=4;i<N;i++)
{
for(int j=1;j<=cnt;j++)
{
if(!f[j].del&&outside(f[j],P[i]))
{
work(j,i);break;
}
}
}
bool use[SIZEN]={0};
for(int i=1;i<=cnt;i++)
{
if(!f[i].del) use[f[i].x]=use[f[i].y]=use[f[i].z]=1;
}
int ans=N;
for(int i=0;i<N;i++) ans-=use[i];
printf("%d\n",ans);
}
void work()
{
if(M==1) calc_0();
if(M==2) calc_1();
if(M==3) calc_2();
if(M==4) calc_3();
}
int main()
{
freopen("nt2011_spring.in","r",stdin);
freopen("nt2011_spring.out","w",stdout);
read();
work();
return 0;
}