【POJ-3304-Segments】 判断线段与直线相交情况

POJ-3304-Segments

题意
给你n条线段，求是否有一条直线，满足所有直线在其上面的投影有公共的交点
$1<=n<=100$
做法
首先如果投影有公共的交点，那么如果在那个公共的交点上做垂线，肯定会穿过n条线段，所以我们只要看是否存在一条直线与所有线段都相交即可，而与这n条线断都相交的直线一定经过某两个线段的端点，我们假设这条直线不经过任意一个端点，我们一定可以平移这条直线使它达到某个端点再停止，之后在那个端点上旋转使之达到另一个端点停止，也就是说如果存在这样一条直线，我们只要枚举所有的两个端点所确定的直线，其中一定会有满足的情况，所以我们只要$O(n^2)$枚举所有直线再$o(n)check$是否所有线段都与这条直线相交即可。
代码

#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
using namespace std;const double eps = 1e-8;
const double inf = 1e20;
const double pi = acos(-1.0);
const int maxn = 1005;
const int maxp = 1010;
int sgn(double x)
{
    if (fabs(x) <eps) return 0;if(x <0) return -1;return 1;
}
inline double sqr(double x)
{
    return x * x;
}
struct Point
{
    double x, y;Point() {
    }Point (double _x, double _y){
    x = _x, y = _y;}void input(){
    scanf("%lf%lf", &x, &y);}void output(){
    printf("%.2f %.2f\n", x, y);}bool operator == (Point b) const{
    return sgn(x - b.x) == 0 && sgn(y - b.y) == 0;}bool operator < (Point b) const{
    return sgn(x - b.x) == 0 ? sgn(y - b.y) < 0 : x < b.x;}Point operator - (const Point &b) const{
    return Point(x - b.x, y - b.y);}double operator ^ (const Point &b) const{
    return x * b.y - y * b.x;}double operator * (const Point & b) const{
    return x * b.x + y * b.y;}double len(){
    return hypot(x, y);}double len2(){
    return x * x + y * y;}double distance(Point p){
    return hypot(x - p.x, y - p.y);}Point operator + (const Point &b) const{
    return Point(x + b.x, y + b.y);}Point operator * (const double &k) const{
    return Point(x * k, y * k);}Point operator / (const double &k) const{
    return Point (x / k, y / k);}double rad(Point a, Point b){
    Point p = *this;return fabs(atan2( fabs((a - p) ^ (b - p)), (a - p) * (b - p) ));}Point trunc(double r){
    double l = len();if (!sgn(l)) return *this;r /= l;return Point(x * r, y * r);}
};
struct Line
{
    Point s, e;Line() {
    }Line(Point _s, Point _e){
    s = _s, e = _e;}bool operator == (Line v){
    return (s == v.s) && (e == v.e);}Line (Point p, double angle){
    s = p;if (sgn(angle - pi / 2) == 0)e = (s + Point (0, 1));elsee = (s + Point (1, tan(angle)));}Line(double a, double b, double c){
    if (sgn(a) == 0){
    s = Point(0, -c / b);e = Point(1, -c / b);}else if (sgn(b) == 0){
    s = Point(-c / a, 0);e = Point(-c / a, 1);}else{
    s = Point(0, -c / b);e = Point(1, (-c-a) / b);}}void input(){
    s.input();e.input();}void adjust(){
    if (e < s) swap(s, e);}double length(){
    return s.distance(e);}double angle(){
    double k = atan2(e.y - s.y, e.x - s.x);if (sgn(k) < 0) k += pi;if (sgn(k - pi) == 0) k -= pi;return k;}int relation(Point p){
    int c = sgn( (p - s) ^ (e - s) );if (c < 0) return 1;else if (c > 0) return 2;return 3;}bool pointonseg(Point p){
    return sgn((p - s) ^ (e - s)) == 0 && sgn((p - s) * (p - e)) <= 0;}bool parallel(Line v){
    return sgn((e - s) ^ (v.e - v.s)) == 0;}Point lineprog(Point p){
    return s + ( ((e - s) * ((e - s) * (p - s))) / ((e - s).len2()) );}Point symmetrypoint(Point p){
    Point q = lineprog(p);return Point(2.0 * q.x - p.x, 2.0 * q.y - p.y);}double dispointtoline(Point p){
    return fabs((p - s) ^ (e - s)) / length();}int linecrossseg(Line v){
    int d1=sgn((e-s)^(v.s-s));int d2=sgn((e-s)^(v.e-s));if((d1^d2)==-2) return 2;return (d1==0||d2==0);}
};
Point p[maxn];
Line L[maxn];
int main()
{
    int T;scanf("%d", &T);while(T--){
    double xa,ya,xb,yb;int n;scanf("%d",&n);for(int i=1;i<=n;i++){
    scanf("%lf%lf%lf%lf",&xa,&ya,&xb,&yb);p[i]=Point(xa,ya);p[i+n]=Point(xb,yb);L[i]=Line(p[i],p[i+n]);}int ff=0;for(int i=1;i<=2*n;i++){
    for(int j=i;j<=2*n;j++){
    if(p[i]==p[j]) continue;//防止出现两个点重合的情况Line now(p[i],p[j]);int flag=0;for(int k=1;k<=n;k++){
    if(now.linecrossseg(L[k])==0){
    flag=1;break;}}if(flag==0){
    ff=1;break;}}if(ff==1) break;}if(ff==1) puts("Yes!");else puts("No!");}return 0;
}