【题解】POJ3304Segments-计算几何

POJ3304

大致题意

给定个线段，求是否存在一条直线，所有的线段在该直线上的投影都有一个公共点。

思路

题目可以转化为，是否存在一条直线可以穿过所有的线段。我们可以将所有的线段的两个端点全部存在一个数组里，任取两个不同的点构成直线，判断这条直线是否穿过所有线段。如果有一条这样的线段存在就输出Yes!，否则输出No!直线穿过线段可以使用向量和点的有向面积来判断。

代码

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double,double> PDD;
#define fi first
#define se second
#define mp make_pair
#define IOS ios::sync_with_stdio(false),cin.tie(0)
const int N = 200 + 10;
const int MOD = 998244353;
const int INF = 0x3f3f3f3f;
const double eps = 1e-8;


PDD q[N],a[N],b[N];
int n;
int cmp(double x,double y){
    if (fabs(x - y) < eps)    return 0;
    if (x < y)    return -1;
    return 1;
}

int sign(double x){
    if (fabs(x) < eps)    return 0;
    if (x > 0)    return 1;
    return -1;
}

double cross(double x1,double y1,double x2,double y2){
    return (x1 * y2 - x2 * y1);
}

double area(PDD x,PDD y,PDD z){
    return cross(y.fi - x.fi,y.se - x.se,z.fi - x.fi,z.se - x.se);
}

bool check(){
    for (int i = 0;i < 2*n;++i){
        for (int j = i+1;j < 2*n;++j){
            if (!cmp(q[i].fi,q[j].fi) && !cmp(q[i].se,q[j].se)){
                //cout << q[i].fi << " " << q[j].fi << " " << q[i].se << " " << q[j].se << endl;
                continue;
            }
            bool f = 1;
            for (int k = 0;k < n;++k){
                //cout << i << " " << j << " " << k << endl;
                //cout << sign(area(q[i],q[j],a[k])) * sign(area(q[i],q[j],b[k])) << endl;
                if (sign(area(q[i],q[j],a[k])) * sign(area(q[i],q[j],b[k])) > 0){
                    f = 0;
                    break;
                }
            }
            //cout <<  i << " " << j << " " << f << endl;
            if (f)    return true;
        }
    }
    return false;
}


int main(){
    int T;cin >> T;
    while (T--){
        cin >> n;
        for (int i = 0,k = 0;i < n;++i){
            double x1,y1,x2,y2;
            cin >> x1 >> y1 >> x2 >> y2;
            //cout << x1 << x2 << y1 << y2 << endl;
            q[k++] = mp(x1,y1);
            q[k++] = mp(x2,y2);
            //if (k == 4)    cout << q[2].fi << " " << q[2].se << endl;
            a[i] = mp(x1,y1),b[i] = mp(x2,y2);
        }
        if (check())    puts("Yes!");
        else puts("No!");
    }
    return 0;
}