BZOJ2640 : 可见区域

设$base$表示直接能看到的面积,$f[i]$表示仅去掉线段$i$后新增的面积,$g[i][j]$表示仅去掉线段$i$和$j$后新增的面积。

删除一条线段的答案为$base+\max(f[i])$。

删除两条线段的答案为$base+\max(g[i][j]+f[i]+f[j],f最大值+f次大值)$。

转一圈扫描线,按照到原点从近到远用set维护所有存在的线段。

对于相邻两条扫描线中间的部分,找到最近的三条线段$A,B,C$,求出到原点的三角形面积$SA,SB,SC$,则$SA$贡献给$base$,$SB-SA$贡献给$f[A]$,$SC-SB$贡献给$g[A][B]$。

由此可以发现$g$中只有$O(n)$项非$0$,可以暴力枚举。

时间复杂度$O(n\log n)$。

#include<cstdio>
#include<algorithm>
#include<set>
#include<map>
using namespace std;
const int N=100010;
inline int sgn(int x){
if(x>0)return 1;
if(x<0)return -1;
return 0;
}
int n,ce,i,j,cg;bool in[N];
struct P{
int x,y;
P(){}
P(int _x,int _y){x=_x,y=_y;}
int pos()const{return x?x<0:y<0;}
P operator-(const P&b)const{return P(x-b.x,y-b.y);}
void read(){scanf("%d%d",&x,&y);}
}a[N][2],A,B,X,PRE;
struct PD{
double x,y;
PD(){}
PD(double _x,double _y){x=_x,y=_y;}
double len(){return x*x+y*y;}
};
struct E{
P o;int t;
E(){}
E(P _o,int _t){o=_o,t=_t;}
}e[N];
struct Num{
double x;bool inf;
Num(){x=0,inf=0;}
Num(double _x,bool _inf){x=_x,inf=_inf;}
void up(const Num&b){
if(inf)return;
if(b.inf){inf=1;return;}
if(x<b.x)x=b.x;
}
void operator+=(const Num&b){x+=b.x,inf|=b.inf;}
Num operator+(const Num&b)const{return Num(x+b.x,inf|b.inf);}
void write(){if(inf)puts("infinite");else printf("%.2f\n",x/2);}
bool operator<(const Num&b)const{
if(inf!=b.inf)return inf<b.inf;
return x<b.x;
}
}f[N],base,ans,tmp;
typedef pair<int,int>PI;
typedef pair<PI,Num>PIN;
PIN g[N];
inline int cross(const P&a,const P&b){return a.x*b.y-a.y*b.x;}
inline int cmpp(const P&a,const P&b){
if(a.pos()!=b.pos())return a.pos()-b.pos();
return sgn(cross(a,b));
}
inline bool cmpe(const E&a,const E&b){return cmpp(a.o,b.o)<0;}
inline bool has_intersection(const P&a,const P&b,const P&p,const P&q){
int d1=sgn(cross(b-a,p-a)),d2=sgn(cross(b-a,q-a));
int d3=sgn(cross(q-p,a-p)),d4=sgn(cross(q-p,b-p));
if(d1*d2<0&&d3*d4<0)return 1;
return 0;
}
inline PD line_intersection(const P&a,const P&b,const P&p,const P&q){
int U=cross(p-a,q-p),D=cross(b-a,q-p);
double o=1.0*U/D;
return PD(a.x+(b.x-a.x)*o,a.y+(b.y-a.y)*o);
}
inline double area(const PD&a,const PD&b){return -a.x*b.y+a.y*b.x;}
struct cmp{
bool operator()(int x,int y){
double dx=line_intersection(A,X,a[x][0],a[x][1]).len(),
dy=line_intersection(A,X,a[y][0],a[y][1]).len();
return dx<dy;
}
};
set<int,cmp>T;
inline void change(int x){
if(!in[x])T.insert(x);else T.erase(x);
in[x]^=1;
}
inline void solve(){
if(!cmpp(PRE,X))return;
set<int,cmp>::iterator it=T.begin();
static int id[3];
static Num v[3];
int i,o,x,y;
for(i=0;i<3;i++)id[i]=0;
for(i=0;i<3;i++){
if(it==T.end())break;
id[i]=*it;
it++;
}
for(i=0;i<3;i++)if(!id[i])v[i]=Num(0,1);else{
o=id[i];
v[i]=Num(area(line_intersection(A,PRE,a[o][0],a[o][1]),line_intersection(A,X,a[o][0],a[o][1])),0);
}
for(i=2;i;i--)if(!v[i].inf)v[i].x-=v[i-1].x;
base+=v[0];
if(id[0])f[id[0]]+=v[1];
if(id[0]&&id[1]){
x=id[0],y=id[1];
if(x>y)swap(x,y);
g[++cg]=PIN(PI(x,y),v[2]);
}
}
int main(){
scanf("%d",&n);
A=P(0,0);
PRE=X=B=P(0,2000);
for(i=1;i<=n;i++){
a[i][0].read(),a[i][1].read();
if(a[i][0].x>a[i][1].x)swap(a[i][0],a[i][1]);
if(has_intersection(A,B,a[i][0],a[i][1])||a[i][0].x<0&&a[i][1].x==0&&a[i][1].y>0)change(i);
e[++ce]=E(a[i][0],i);
e[++ce]=E(a[i][1],i);
}
sort(e+1,e+ce+1,cmpe);
for(i=1;i<=ce;i++){
X=e[i].o;
solve();
change(e[i].t);
PRE=X;
}
X=B;
solve();
base.write();
ans=Num(0,0);
for(i=1;i<=n;i++)ans.up(f[i]);
ans+=base;
ans.write();
ans=Num(0,0);
sort(g+1,g+cg+1);
for(i=1;i<=cg;i=j){
tmp=f[g[i].first.first]+f[g[i].first.second];
for(j=i;j<=cg&&g[i].first==g[j].first;j++)tmp+=g[j].second;
ans.up(tmp);
}
sort(f+1,f+n+1);
ans.up(f[n]);
if(n>1)ans.up(f[n]+f[n-1]);
ans+=base;
ans.write();
return 0;
}

  

上一篇:Window.open 实现导航与打开窗口,导航到一个特定链接地址,也可以打开一个新的浏览器窗体


下一篇:jQuery实现input框输入值动态搜索