列出不等式后,把同时除Z把它去掉。

注意了,这里应该 是把直线变两点表示的向量更为简单,我开始就直接用直线写,后来,唉,写不下去了。。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;
const int MAX=110;
const double eps=1e-10;
const double inf=1e10; struct point{
double x,y;
};
point operator -(point x,point y){
point t;
t.x=x.x-y.x; t.y=x.y-y.y;
return t;
} double operator *(point x,point y){
return x.x*y.y-x.y*y.x;
} struct line{
point a,b;
double angle;
};
int n,lnum;
double A[MAX],B[MAX],C[MAX];
line le[MAX],st[MAX]; int DB(double d){
if(fabs(d)<eps) return 0;
if(d>0) return 1;
return -1;
} void addLine(double x1,double y1,double x2,double y2){
point a; a.x=x1; a.y=y1;
point b; b.x=x2; b.y=y2;
le[lnum].a=a; le[lnum].b=b;
le[lnum].angle=atan2(y2-y1,x2-x1);
} bool cmp( line x, line y){
if(fabs(x.angle-y.angle)<eps){
if((y.b-x.a)*(x.b-y.a)>eps)
return true;
return false;
}
return x.angle<y.angle;
} void getIntersect(line l1, line l2, point& p) {
double dot1,dot2;
dot1 = (l1.b-l2.a)*(l1.a-l2.a);
dot2 = (l2.b-l1.b)*( l1.a-l1.b);
p.x = (l2.a.x * dot2 + l2.b.x * dot1) / (dot2 + dot1);
p.y = (l2.a.y * dot2 + l2.b.y * dot1) / (dot2 + dot1);
} bool judge(line l0, line l1, line l2) {
point p;
getIntersect(l1, l2, p);
return DB((l0.a-p)*(l0.b-p)) <=0;
} bool pare(line x,line y){
return fabs((x.b-x.a)*(y.b-y.a))<eps;
} bool half(){
int top=1,bot=0;
sort(le,le+lnum,cmp);
int tmp=1;
for(int i=1;i<lnum;i++){
if(fabs(le[i].angle-le[tmp-1].angle)>eps) le[tmp++]=le[i];
}
lnum=tmp;
st[0]=le[0]; st[1]=le[1];
for(int i=2;i<lnum;i++){
while(bot<top&&judge(le[i], st[top-1], st[top])) top--;
while(bot<top&&judge(le[i],st[bot+1],st[bot])) bot++;
st[++top]=le[i];
}
while(bot<top&&judge(st[bot],st[top-1],st[top])) top--;
while(bot<top&&judge(st[top],st[bot+1],st[bot])) bot++;
if(top<=bot+1) return false;
return true;
} bool slove(int s){
int i, j, k;
double x1, y1, x2, y2, a, b, c;
lnum=0;
addLine(0, 0, inf, 0 ); lnum++;
addLine(inf, 0, inf, inf ); lnum++;
addLine(inf, inf, 0, inf ); lnum++;
addLine(0, inf, 0, 0 ); lnum++;
for (j = 0; j < n; j++)
if (s != j) {
a = 1.0 / A[j] - 1.0 / A[s];
b = 1.0 / B[j] - 1.0 / B[s];
c = 1.0 / C[j] - 1.0 / C[s];
int d1 = DB(a);
int d2 = DB(b);
int d3 = DB(c);
if (!d1) {
if (!d2) {
if (d3 <= 0) {
return false;
}
continue;
}
x1 = 0;
x2 = d2;
y1 = y2 = - c / b;
}
else {
if (!d2) {
x1 = x2 = - c / a;
y1 = 0;
y2 = -d1;
}
else {
x1 = 0; y1 = - c / b;
x2 = d2;
y2 = -(c + a * x2) / b;
}
}
addLine(x1, y1, x2, y2 );
lnum++;
}
if(!half()) return false;
return true;
} int main(){
while(scanf("%d",&n)!=EOF){
for(int i=0;i<n;i++)
scanf("%lf%lf%lf",&A[i],&B[i],&C[i]);
for(int i=0;i<n;i++){
if(slove(i)) printf("Yes\n");
else printf("No\n");
}
}
return 0;
}

  

05-21 13:07