BZOJ1829 : [Usaco2010 Mar]starc星际争霸
设出$x,y,z$三个未知量分别表示三种单位的战斗力。
那么各种不等式都可以表示成$ax+by+cz\geq 0$的形式。
注意到$z>0$，那么两边都除以$z$得到$ax+by+c\geq 0$。
然后半平面交求出所有顶点后，对于每次询问将所有顶点带入求值即可。
#include
#include
#include
using namespace std;
const int N=400;
const double eps=1e-10;
struct P{double x,y;P(){x=y=0;}P(double _x,double _y){x=_x,y=_y;}P operator-(const P&a)const{return P(x-a.x,y-a.y);}P operator+(const P&a)const{return P(x+a.x,y+a.y);}P operator*(double a)const{return P(x*a,y*a);}
}p[N],a[N];
struct L{P p,v;double a;L(){}L(P _p,P _v){p=_p,v=_v;}bool operator<(const L&b)const{return ab的逆时针方向
inline void newL(const P&a,const P&b){line[++cl]=L(a,b-a);}
inline bool left(const P&p,const L&l){return cross(l.v,p-l.p)>0;}
inline P pos(const L&a,const L&b){P x=a.p-b.p;double t=cross(b.v,x)/cross(a.v,b.v);return a.p+a.v*t;
}
inline void halfplane(){for(int i=1;i<=cl;i++)line[i].cal();sort(line+1,line+cl+1);h=t=1;q[1]=line[1];for(int i=2;i<=cl;i++){while(h0)newL(A,B);else newL(B,A);}else{P A=P(-1.0*c/a,0),B=P(-1.0*c/a,100),C=A;C.x-=1;if(C.x*a+C.y*b+c>0)newL(A,B);else newL(B,A);}}halfplane();while(m--){int a,b,c,d,e,f;scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f);a-=d,b-=e,c-=f;int flag=0;for(int i=h;i<=t;i++){double tmp=p[i].x*a+p[i].y*b+c;if(tmp>-eps)flag|=1;if(tmp
转载于:https://www.cnblogs.com/clrs97/p/4951737.html
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！