| Time Limit: 1000MS | Memory Limit: 65536KB | 64bit IO Format: %I64d & %I64u |
Description
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.
Sample Input
3 2 1.0 2.0 3.0 4.0 4.0 5.0 6.0 7.0 3 0.0 0.0 0.0 1.0 0.0 1.0 0.0 2.0 1.0 1.0 2.0 1.0 3 0.0 0.0 0.0 1.0 0.0 2.0 0.0 3.0 1.0 1.0 2.0 1.0
Sample Output
Yes! Yes! No!
题意：给出若干条线段，若存在一条直线，使所有的线段的投影到这条直线上，都有公共点（至少一个）,那么就输出yes，如果不存在则输出no
假如存在这条直线，那么经过投影的公共点与这条直线垂直的直线必和所有的线段相交。原题可以转化为求直线与线段相交的问题。因为投影在直线有公共区域，公共区域的范围一定是所有线段的端点的其中两个端点所投影成的两个极端，只要找到这两个端点，并连成直线，直线就可以串插所有的线段。
Source
Code
| Problem: C | User: sdau_09_zys | |
| Memory: 252 KB | Time: 32 MS | |
| Language: C++ | Result: Accepted | |
| Public: | ||
#include<iostream>
using namespace std;#define eps 1e-8
#define zero(x) (((x)>0?(x):(-x))<eps)
#define MAX 105
struct point //点
{
double x;
double y;
}p[MAX+MAX];struct line //直线
{
point a;
point b;
}l[MAX];int dblcmp(double d) //判断d是否为0，如果是0，返回0，如果大于0，返回1，如果小于0，返回-1
{
if(zero(d)) return 0;
else return (d>0)? 1:-1;
}double det(double x1,double y1,double x2,double y2) //计算叉积
{
return x1*y2-x2*y1;
}double cross(point a,point b,point c) //还是计算叉积
{
return det(b.x-a.x,b.y-a.y,c.x-a.x,c.y-a.y);
}bool run(int n)
{
int d1,d2;
int i,j,k;
for(i=0;i<2*n-1;i++) //找第一个端点
for(j=i+1;j<2*n;j++) //找第二个端点
{
if(!(dblcmp(p[i].x-p[j].x)||dblcmp(p[i].y-p[j].y))) continue; //如果第一和第二个端点相同，跳过
for(k=0;k<n;k++) //找出所有直线，并且上述两端点做比较
{
d1=dblcmp(cross(p[i],l[k].a,p