蓝书半平面交例题
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=;
const double eps=1e-;
int n;
struct vec{
double x,y;
vec(double x=,double y=):x(x),y(y){}
vec operator-(vec& a){
return vec(x-a.x,y-a.y);
}
vec operator+(vec&a){
return vec(x+a.x,y+a.y);
}
}po[maxn],v[maxn],v2[maxn],g[maxn];
vec operator*(vec a,double t){return vec(a.x*t,a.y*t);}
double cross(vec a,vec b){return a.x*b.y-b.x*a.y;}
struct lin{
vec p,v;
double ang;
lin(){}
lin(vec p,vec v):p(p),v(v){ang=atan2(v.y,v.x);}
bool operator<(const lin&a)const{
return ang<a.ang;
}
}ll[maxn],q[maxn];
bool onl(lin L,vec p){
return cross(L.v,p-L.p)>;
}
vec qj(lin a,lin b){
vec u=a.p-b.p;
double t=cross(b.v,u)/cross(a.v,b.v);
return a.v*t+a.p;
}
vec nor(vec a){
double len=sqrt(a.x*a.x+a.y*a.y);
return vec(-a.y/len,a.x/len);
}
int halfj(){
sort(ll,ll+n);
int head,tail;
q[head=tail=]=ll[];
for(int i=;i<n;++i){
while(head<tail&&!onl(ll[i],g[tail-]))tail--;
while(head<tail&&!onl(ll[i],g[head]))head++;
q[++tail]=ll[i];
if(fabs(cross(q[tail].v,q[tail-].v))<eps){
--tail;if(onl(q[tail],ll[i].p))q[tail]=ll[i];
}
if(head<tail)g[tail-]=qj(q[tail-],q[tail]);
}
while(head<tail&&!onl(q[head],g[tail-]))--tail;
if(tail-head<=)return ;
return ;
}
int main(){
while(scanf("%d",&n)==&&n){
int m,x,y;
for(int i=;i<n;++i){
scanf("%d%d",&x,&y);po[i]=vec(x,y);
}
for(int i=;i<n;++i){v[i]=po[(i+)%n]-po[i];v2[i]=nor(v[i]);}
double l=,r=,mid;
while(r-l>1e-){
mid=(l+r)/;
for(int i=;i<n;++i)ll[i]=lin(v2[i]*mid+po[i],v[i]);//这里必须先写乘法再写加法才能过编译，可能是我这种重定义的问题；
if(halfj())l=mid;else r=mid;
}
printf("%.6lf\n",l);
}
system("pause");
return ;
}
/*
4
0 0
10000 0
10000 10000
0 10000
3
0 0
10000 0
7000 1000
6
0 40
100 20
250 40
250 70
100 90
0 70
3
0 0
10000 10000
5000 5001
0
*/