bzoj 3190 赛车 半平面交

   直接写的裸的半平面交,已经有点背不过模板了。。。

   这题卡精度,要用long double ,esp设1e-20。。。

   

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#define N 20005
#define double long double
#define inf 1e100
using namespace std;
int n;
const double eps = 1e-;
struct point// 点&向量
{
double x,y;
point(){};
point(double _x,double _y)
{
x=_x;y=_y;
}
}p[N];
// 点减点=向量
point operator - (point a,point b){return point(a.x-b.x,a.y-b.y);}
// 向量+向量=向量 点+向量=点
point operator + (point a,point b){return point(a.x+b.x,a.y+b.y);}
// 向量数乘
point operator * (point a,double b){return point(a.x*b,a.y*b);}
point operator / (point a,double b){return point(a.x/b,a.y/b);}
// 叉积
double cross(point a,point b){return a.x*b.y-a.y*b.x;}
int dcmp(double x)
{
if(max(x,-x)<eps)return ;
if(x<)return -;
return ;
}
struct line
{
point p,v;
int id;
double ang;
line(){};
line(point pp,point vv,int _id)
{
id=_id;
p=pp;v=vv;
ang=atan2(v.y,v.x);
}
friend bool operator < (line aa,line bb)
{
return aa.ang<bb.ang;
}
}lines[N],dep[N*];int cnt;
point getpoint(line a,line b)
{
point u=a.p-b.p;
double t=cross(b.v,u)/cross(a.v,b.v);
return a.p+a.v*t;
}
bool onright(point a,line b)
{
return cross(b.v,a-b.p)<;
}
int tot,h,t;
void insert(line l)
{
while(h<t&&onright(p[t-],l))t--;
while(h<t&&onright(p[h],l))h++;
dep[++t]=l;
if(h<t&&dcmp(dep[t].ang-dep[t-].ang)==)
{
t--;
if(onright(dep[t].p,l))dep[t]=l;
}
if(h<t)p[t-]=getpoint(dep[t],dep[t-]);
}
void half()
{
h=;t=;
for(int i=;i<=cnt;i++)
{
insert(lines[i]);
}
while(h<t&&onright(p[t-],dep[h]))t--;
return ;
}
int v[N],pos[N];
int tt[N];
map<pair<int,int>,int>mp;
vector<int>ss[N];
int main()
{
// freopen("in.txt","r",stdin);
lines[++cnt]=line(point(inf,inf),point(-,),);
lines[++cnt]=line(point(,inf),point(,-),);
lines[++cnt]=line(point(,),point(,),);
lines[++cnt]=line(point(inf,),point(,),);
// 保证答案为空集或一个凸多边形
scanf("%d",&n);int mx=;int ans=;
for(int i=;i<=n;i++)scanf("%d",&pos[i]),mx=max(mx,pos[i]);
for(int i=;i<=n;i++)scanf("%d",&v[i]);
for(int i=;i<=n;i++)
{
// if(i==6501){cout<<pos[i]<<' '<<v[i]<<endl;}
if(pos[i]==mx)tt[++ans]=i;
if(mp.find(make_pair(pos[i],v[i]))!=mp.end())ss[mp[make_pair(pos[i],v[i])]].push_back(i);
else mp[make_pair(pos[i],v[i])]=i,lines[++cnt]=line(point(,(double)pos[i]),point(1.0,(double)v[i]),i);
}
sort(lines+,lines+cnt+);
half();
for(int i=h;i<=t;i++)
{
if(dep[i].id!=)
{
int ttt=dep[i].id;
if(pos[ttt]!=mx)tt[++ans]=ttt;
for(int j=;j<ss[ttt].size();j++)
{
if(pos[ss[ttt][j]]!=mx)
{
tt[++ans]=ss[ttt][j];
}
}
}
}
printf("%d\n",ans);
sort(tt+,tt+ans+);
for(int i=;i<ans;i++)printf("%d ",tt[i]);
printf("%d",tt[ans]);
return ;
}
上一篇:C# .Net 多进程同步 通信 共享内存 内存映射文件 Memory Mapped 转


下一篇:web即时通讯2--基于Spring websocket达到web聊天室