| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
还是叉积。#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: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator