洛谷P4250 [SCOI2015]小凸想跑步(半平面交)

题面

传送门

题解

设\(p\)点坐标为\(x_p,y_p\),那么根据叉积可以算出它与\((i,i+1)\)构成的三角形的面积

为了保证\(p\)与\((0,1)\)构成的面积最小,就相当于它比其它所有的三角形构成的面积都要小。如果\(p\)与\((0,1)\)构成的面积比\((i,i+1)\)小,代入叉积计算公式,有

\[(y_0-y_1-y_i+y_{i+1})x_p+(x_1-x_0-x_{i+1}+x_i)y_p+(x_0y_1-x_1y_0-x_iy_{i+1}+x_{i+1}y_i) < 0
\]

然后我们知道对于形如\(Ax+By+C<0\)的线性规划,向量\((-B,A)\)代表的就是这个线性规划的半平面

直接半平面交求解就行了

//minamoto
#include<bits/stdc++.h>
#define R register
#define inline __attribute__((always_inline))
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
using namespace std;
char buf[1<<21],*p1=buf,*p2=buf;
inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
int read(){
R int res,f=1;R char ch;
while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');
return res*f;
}
char sr[1<<21],z[20];int C=-1,Z=0;
inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
void print(R int x){
if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;
while(z[++Z]=x%10+48,x/=10);
while(sr[++C]=z[Z],--Z);sr[++C]='\n';
}
const int N=2e5+5;const double eps=1e-10;
inline int sgn(R double x){return x<-eps?-1:x>eps;}
inline double abs(R double x){return x<-eps?-x:x;}
struct node{
double x,y;
inline node(){}
inline node(R double xx,R double yy):x(xx),y(yy){}
inline node operator +(const node &b)const{return node(x+b.x,y+b.y);}
inline node operator -(const node &b)const{return node(x-b.x,y-b.y);}
inline double operator *(const node &b)const{return x*b.y-y*b.x;}
inline node operator ^(const double &b)const{return node(x*b,y*b);}
}p[N],s[N];
struct Line{
node p,v;double ang;
inline Line(){}
inline Line(R node pp,R node vv):p(pp),v(vv){ang=atan2(v.y,v.x);}
inline bool operator <(const Line &b)const{return sgn(ang-b.ang)?sgn(ang-b.ang)<0:sgn(v*(b.p-p))<0;}
friend node cross(const Line &a,const Line &b){return a.p+(a.v^(b.v*(b.p-a.p)/(b.v*a.v)));}
inline bool Right(R node &b){return sgn(v*(b-p))<0;}
}L[N],q[N];
int n,m,tot,h,t;double area,res;
void HalfPlane(){
sort(L+1,L+1+m);
q[h=t=1]=L[1];
fp(i,2,m)if(sgn(L[i].ang-L[i-1].ang)){
while(h<t&&L[i].Right(p[t-1]))--t;
while(h<t&&L[i].Right(p[h]))++h;
q[++t]=L[i];
if(h<t)p[t-1]=cross(q[t],q[t-1]);
}
while(h<t&&q[h].Right(p[t-1]))--t;
if(t-h+1<=2)return;
p[t]=cross(q[t],q[h]),p[t+1]=p[h];
fp(i,h,t)res+=p[i]*p[i+1];
}
int main(){
// freopen("testdata.in","r",stdin);
n=read();
fp(i,0,n-1)s[i].x=read(),s[i].y=read();
s[n]=s[0];
fp(i,1,n-1)area+=(s[i]-s[0])*(s[i+1]-s[0]);
fp(i,0,n-1)L[++m]=Line(s[i],s[i+1]-s[i]);
fp(i,1,n-1){
double a=s[0].y-s[1].y+s[i+1].y-s[i].y;
double b=s[1].x-s[0].x-s[i+1].x+s[i].x;
double c=s[0].x*s[1].y-s[1].x*s[0].y+s[i+1].x*s[i].y-s[i].x*s[i+1].y;
L[++m]=Line(sgn(b)?node(0,-c/b):node(-c/a,0),node(-b,a));
}
HalfPlane();
printf("%.4lf\n",res/area);
return 0;
}
上一篇:jQuery Chosen 使用


下一篇:jquery chosen onchange 值改变时触发方法