Description
Input
Output
Sample Input
5 1.5 1.5 2.0 1.0 1.0 2.0 2.0 1.75 2.0 1.0 3.0 0.0 2.0 5 1.5 1.5 2.0 1.0 1.0 2.0 2.0 1.75 2.5 1.0 3.0 0.0 2.0 1
Sample Output
HOLE IS ILL-FORMED PEG WILL NOT FIT
这题刚开始想的是从后面往回判断相交的，不过……不行，应该是从前往后判断才对，其中的原因可以画图来看……
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <list>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#define PI acos(-1.0)
#define eps 1e-8
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define pri(a) printf("%d\n",a)
#define f(i,a,n) for(i=a;i<n;i++)
#define F(i,a,n) for(i=a;i<=n;i++)
#define MM 100005
#define MN 505
#define INF 10000007
using namespace std;
typedef long long ll;
inline double sqr(const double &x){ return x * x;}
inline double sgn(const double &x){ return x < -eps ? -1 : x > eps;}
struct Point{
double x, y;
Point(const double &x = 0, const double &y = 0):x(x), y(y){}
Point operator - (const Point &a)const{ return Point(x - a.x, y - a.y);}
Point operator + (const Point &a)const{ return Point(x + a.x, y + a.y);}
Point operator * (const double &a)const{ return Point(x * a, y * a);}
Point operator / (const double &a)const{ return Point(x / a, y / a);}
bool operator < (const Point &a)const{ return sgn(x - a.x) < 0 || (sgn(x - a.x) == 0 && sgn(y - a.y) < 0);}
friend double det(const Point &a, const Point &b){ return a.x * b.y - a.y * b.x;}
friend double dot(const Point &a, const Point &b){ return a.x * b.x + a.y * b.y;}
friend double dist(const Point &a, const Point &b){ return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));}
double len(){ return sqrt(dot(*this, *this));}
Point rotateA(const double &angle)const{ return rotateS(cos(angle), sin(angle));}
Point rotateS(const double &cosa, const double &sina)const{ return Point(x * cosa - y * sina, x * sina + y * cosa);}
void in(){ scanf("%lf %lf", &x, &y); }
void out()const{ printf("%.2f %.2f\n",x, y);}
};
struct Line{
Point s, t;
Line(const Point &s = Point(), const Point &t = Point()):s(s), t(t){}
Point dire()const{ return t - s;}
double len()const{ return dire().len();}
bool isPointInLine(const Point &p)const{ return sgn(det(p - s, t - s)) == 0 && sgn(dot(p - s, p - t)) <= 0;}
bool isPointInLineEx(const Point &p)const{ return sgn(det(p - s, t - s)) == 0 && sgn(dot(p - s, p - t)) < 0;}//不含端点
Point pointProjLine(const Point &p){ return s + dire() * ((dot(p - s, dire()) / dire().len()) /(dire().len()));}
double pointDistLine(const Point &p){ return fabs(det(p - s, dire()) / dire().len());}
friend bool sameSide(const Line &line , const Point &a, const Point &b){
return sgn(det(b - line.s, line.dire())) * sgn(det(a - line.s, line.dire())) > 0;
}
friend bool isLineInsectLine(const Line &l1, const Line &l2){
if(sgn(det(l2.s - l1.s, l1.dire())) == 0 && sgn(det(l2.t - l1.s, l1.dire())) == 0
&& sgn(det(l1.s - l2.s, l2.dire())) == 0 && sgn(det(l1.t - l2.s, l2.dire())) == 0){
return l1.isPointInLine(l2.s) || l1.isPointInLine(l2.t) || l2.isPointInLine(l1.s) ||l2.isPointInLine(l1.t);
}
return !sameSide(l1, l2.s, l2.t) && !sameSide(l2, l1.s, l1.t);
}
friend Point lineInsectLine(const Line &l1, const Line &l2){
double s1 = det(l1.s - l2.s, l2.dire()), s2 = det(l1.t - l2.s, l2.dire());
return (l1.t * s1 - l1.s * s2) / (s1 - s2);
}
void in(){ s.in(); t.in();}
void out()const{ s.out(); t.out(); }
};
Point a[MM][2];
int vis[MM],s[MM];
int main()
{
int n;
while(sca(n)&&n)
{
Line b,b1;
int k=0,i,j;
mem(vis,0);
for(i=1;i<=n;i++)
a[i][0].in(),a[i][1].in();
for(i=1;i<=n;i++)
{
if(vis[i]) continue;
int flag=0;
b.s=a[i][0],b.t=a[i][1];
for(j=i+1;j<=n;j++)
{
if(!vis[j])
{
b1.s=a[j][0],b1.t=a[j][1];
if(isLineInsectLine(b,b1))
{
vis[i]=1; flag=1;
break;
}
}
}
if(!flag) s[k++]=i;
}
printf("Top sticks: ");
for(i=0;i<k;i++)
if(i!=k-1) printf("%d, ",s[i]);
else printf("%d.\n",s[i]);
}
return 0;
}
CUGB计算几何专题：B - A Round Peg in a Ground Hole判断线段相交,布布扣,bubuko.com
CUGB计算几何专题：B - A Round Peg in a Ground Hole判断线段相交
原文：http://blog.csdn.net/u011466175/article/details/20868743