POJ 3304 Segments

Title Link

Given n segments in the two dimensional space, write a program, which determines if there exists a line such that after projecting these segments on it, all projected segments have at least one point in common.

Input
Input begins with a number T showing the number of test cases and then, T test cases follow. Each test case begins with a line containing a positive integer n ≤ 100 showing the number of segments. After that, n lines containing four real numbers x1 y1 x2 y2 follow, in which (x1, y1) and (x2, y2) are the coordinates of the two endpoints for one of the segments.

Output
For each test case, your program must output "Yes!", if a line with desired property exists and must output "No!" otherwise. You must assume that two floating point numbers a and b are equal if |a - b| < 10-8.

1. The problem is very simple: give n line segments, judge whether there is a line in the two-dimensional coordinate system, so that the projection of all line segments on the line meets at least one point

2. On the contrary, draw a straight line first, and assume that in the worst case, if all projections have only one point, and construct several line segments randomly, it will be found that there is an endpoint on the straight line passing through the projection point. Then it is expanded into a segment of repeated projection line segment, and some segments satisfying the conditions are constructed. It can be found that there are two endpoints of the segment to make the line pass through all segments. Moreover, the number of line segments given is not very large, so it is necessary to guess whether the straight line composed of any two endpoints passes through all the line segments directly

3. The method to judge the intersection of line segment and line is a fast repulsion experiment. When do I summarize in the introduction calculation Blog on various problems of lines and line segments , the biggest pit of this problem is that there may be line segments sharing endpoints. We know that when enumerating, we must specifically determine whether two points are duplicate points, but the following method is obviously not good, because it only guarantees not enumerating itself, but there may be duplicate points later, unless this method is used after discretization

for(int i=0;i<num && !flag;i++)
	for(int j=0;j<i && !flag;j++)

Code:

#include <iostream>
#include <math.h>
using namespace std;
#define Point Vector
#define Line Seg
const double eps=1e-8;

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

struct Point{
    double x,y;
    Point(double x=0,double y=0):x(x),y(y){}
    Point operator + (Point p){ return Point(x+p.x,y+p.y); }
    Point operator - (Point p){ return Point(x-p.x,y-p.y); }
    Point operator * (double d){ return Point(x*d,y*d); }
    double operator * (Point p){ return x*p.x+y*p.y; }
    Point operator / (double d){ return Point(x/d,y/d); }
    double operator ^ (Point p){ return x*p.y-y*p.x; }
    bool operator == (const Point &p) const { return dcmp(x-p.x)==0 && dcmp(y-p.y)==0; }
};

double dis(Point a,Point b){
    return sqrt((b-a)*(b-a));
}

struct Line{
    Point p,q;
    Vector v;
    Line(){}
    Line(Point a,Point b){
        p=a,q=b,v=b-a;
    }
};

bool isOnLine(Point p,Line l){
    return dcmp((l.p-p)^(l.q-p))==0?true:false;
}

bool isSegLineInter(Seg s,Line l){
    double c1=l.v^(s.p-l.p),c2=l.v^(s.q-l.p);
    return dcmp(c1)*dcmp(c2)<=0;
}

Point t[1005];
Seg s[200];

int main()
{
    int kase,n;
    double a,b,c,d;
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>kase;
    while(kase--){
        cin>>n;
        int num=0,cnt=0;
        Point aa,bb;
        while(n--){
            cin>>a>>b>>c>>d;
            aa=Point(a,b),bb=Point(c,d);
            t[num++]=aa;
            t[num++]=bb;
            s[cnt++]=Line(aa,bb);
        }
        int flag=0;
        for(int i=0;i<num && !flag;i++){
            for(int j=0;j<num && !flag;j++){
                if(dcmp(dis(t[i],t[j]))==0) continue;  //Pits!!!
                flag=1;
                Line l=Line(t[i],t[j]);
                for(int k=0;k<cnt;k++){
                    if(!isSegLineInter(s[k],l)){
                        flag=0;
                        break;
                    }
                }
            }
        }
        if(flag) cout<<"Yes!\n";
        else cout<<"No!\n";
    }

    return 0;
}
Published 127 original articles, won praise 7, visited 5224
Private letter follow

Tags: iOS

Posted on Thu, 12 Mar 2020 04:08:00 -0700 by larsojl