poj 3304 找一条直线穿过所有线段

题目链接:http://poj.org/problem?id=3304

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn = ;
const int maxe = ;
const int INF = 0x3f3f3f;
const double eps = 1e-;
const double PI = acos(-1.0); struct Point{
double x,y;
Point(double x=, double y=) : x(x),y(y){ } //构造函数
};
typedef Point Vector; Vector operator + (Vector A , Vector B){return Vector(A.x+B.x,A.y+B.y);}
Vector operator - (Vector A , Vector B){return Vector(A.x-B.x,A.y-B.y);}
Vector operator * (Vector A , double p){return Vector(A.x*p,A.y*p);}
Vector operator / (Vector A , double p){return Vector(A.x/p,A.y/p);} bool operator < (const Point& a,const Point& b){
return a.x < b.x ||( a.x == b.x && a.y < b.y);
}
int dcmp(double x){
if(fabs(x) < eps) return ;
else return x < ? - : ;
}
bool operator == (const Point& a, const Point& b){
return dcmp(a.x - b.x) == && dcmp(a.y - b.y) == ;
} double Dot(Vector A, Vector B){ return A.x*B.x + A.y*B.y; }
double Cross(Vector A, Vector B) { return A.x*B.y - A.y * B.x; }
double Length(Vector A) { return sqrt(Dot(A,A)); } bool SegmentLineIntersection(Point a1,Point a2,Point b1,Point b2){ //a1a2是直线,b1b2是线段;
double c1 = Cross(a2-a1,b1-a1), c2 = Cross(a2-a1,b2-a1); return dcmp(c1) * dcmp(c2) < || dcmp(c1) == || dcmp(c2) == ;
} Point read_point(){
Point A;
scanf("%lf %lf",&A.x,&A.y);
return A;
} /******************************分割线*******************************/ Point P[maxn][];
int n; int main()
{
//freopen("E:\\acm\\input.txt","r",stdin);
int T;
cin>>T;
while(T--){
cin>>n;
for(int i=;i<=n;i++){
P[i][] = read_point();
P[i][] = read_point();
}
bool ans = false;
for(int i=;i<n;i++)
for(int k=;k<=;k++)
for(int j=i+;j<=n;j++)
for(int m=;m<=;m++){ //确定两个端点P[i][k]和P[j][m];接下来判断过这两点直线是否穿过所有线段;
if(P[i][k] == P[j][m]) continue;
int s;
for(s=;s<=n;s++){
if(!SegmentLineIntersection(P[i][k],P[j][m],P[s][],P[s][])) break;
}
if(s == n+) { ans = true; goto print; }
} print:
if(ans || n==) printf("Yes!\n"); //n == 1没考虑,WA了两次看discuss别人说的;
else printf("No!\n");
}
}
上一篇:css清楚浮动的方法


下一篇:类似Visual Studio一样,使用Qt Creator管理多个项目,创建子项目