半平面交+二分
二分最远距离把每个直线往里移这个距离然后看一下半平面交是否存在就好
然后注意精度问题 【poj G++需要用%f C++没有问题
//Love and Freedom.#include#include#include#include#define inf 20021225#define ll long long#define db double#define eps 1e-6#define N 1010using namespace std;struct poi{ db x,y; poi(){} poi(db _x,db _y){x=_x,y=_y;}};typedef poi vec;vec operator +(vec a,vec b){return vec(a.x+b.x,a.y+b.y);}vec operator -(vec a,vec b){return vec(a.x-b.x,a.y-b.y);}vec operator *(vec a,db b){return vec(a.x*b,a.y*b);}db cross(vec a,vec b){return a.x*b.y-a.y*b.x;}db dis(vec a){return sqrt(a.x*a.x+a.y*a.y);}struct line{ poi p; vec v; db ang; line(){} line(poi p1,poi p2){p=p1; v=p2-p1; ang=atan2(v.y,v.x);}}r[N],l[N];void put(poi a){ printf("%lf %lf\n",a.x,a.y);}void putl(line l){ printf("----line----\n"); put(l.p); put(l.v); printf("%lf\n",l.ang);}poi section(line a,line b){ db k = cross(a.p-b.p,a.p+a.v-b.p)/(cross(a.p-b.p,b.v)+cross(b.v,a.p+a.v-b.p)); return b.p+b.v*k;}bool onleft(line a,poi b){return cross(a.p+a.v-b,a.p-b)