Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 还是叉积。

Posted by dengyaolong at 2014-05-03 22:25:49 on Problem 3304
```#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
using namespace std;
#define rc  1e-8
int N;
template<typename T>
class Point{
public:
T x;
T y;
Point(){};
bool operator == (const Point &p)const{
if(abs(x-p.x)<rc&&abs(y-p.y)<rc){
return true;
}
return false;

}
};
template<typename T>
class Line{
public:
Line(){}
void set(T l,T u,T r,T d){
lu.x=l;lu.y=u;
rd.x=r;rd.y=d;
}

Point<T> lu,rd;

};
vector<Line<double> > v(105);
template<typename T>
T mult(Point<T> &sp,Point<T> &ep,Point<T> &op){
return (op.x-sp.x)*(sp.y-ep.y)-(op.y-sp.y)*(sp.x-ep.x);

}

template<typename T>
bool cross(Point<T> &p1,Point<T> &p2){
if(p1==p2) return false;
for(int i=0;i<N;i++){
if(mult(p1,p2,v[i].lu)*mult(p1,p2,v[i].rd)>rc){
return false;
}
}
return true;
}
bool judge(int i,int j){
if(cross(v[i].lu,v[j].lu))
return true;
if(cross(v[i].lu,v[j].rd))
return true;
if(cross(v[i].rd,v[j].lu))
return true;
if(cross(v[i].rd,v[j].rd))
return true;
return false;

}
bool solve(){
if(N<3) return true;
for(int i=0;i<N-1;i++)
for(int j=i+1;j<N;j++)
if(judge(i,j)){
return true;
}
return false;
}
int main()
{
int T;
double l,d,r,u;
int i;
scanf("%d",&T);
while(T--){

scanf("%d",&N);
for(i=0;i<N;i++){
scanf("%lf%lf%lf%lf",&l,&u,&r,&d);
v[i].set(l,u,r,d);
}
if(solve()){
puts("Yes!");
}else{
puts("No!");

}
}
return 0;
}
```

Followed by: