专题十三 基础计算几何

POJ 2318 TOYS

分析：就是让你找每个盒子里面有几个玩具，由于坐标都是整数，处理更加简单，二分+叉积判断位置。

#include<iostream>
#include<cstdio>
#include<iomanip>
#include<cstring>
#include<vector>
#include<map>
#include<queue>
#include<set>
#include<algorithm>
#include<cmath>
using namespace std;
const int MAXN=5000+10;
int sgn(int x){
    if(x==0) return 0;
    if(x<0) return -1;
    else return 1;
}
struct Point{
    int x,y;
    Point(){}
    Point(int x,int y):x(x),y(y){}
    Point operator-(const Point& b)const{
        return Point(x-b.x,y-b.y);
    }
    //叉积
    int operator ^(const Point &b)const{
        return x*b.y-y*b.x;
    } 
};
int n,m;
struct Line{
    Point up,down;
    Line(){}
    Line(Point up,Point down):up(up),down(down){}
}box[MAXN];
int num[MAXN];
void BinSearch(Point p){
    int L=0,R=n+1,ans;
    while(L<=R){
        int mid=L+((R-L)>>1);
        if(sgn((box[mid].up-p)^(box[mid].down-p))<0){
            ans=mid;
            R=mid-1;
        }else{
            L=mid+1;
        }
    }
    num[ans-1]++;
}
int main(){
    while(~scanf("%d",&n)&&n){
        int x1,y1,x2,y2,x,y;
        scanf("%d%d%d%d%d",&m,&x1,&y1,&x2,&y2);
        box[0]=Line(Point(x1,y1),Point(x1,y2));
        box[n+1]=Line(Point(x2,y1),Point(x2,y2));
        for(int i=1;i<=n;i++){
            scanf("%d%d",&box[i].up.x,&box[i].down.x);
            box[i].up.y=y1; box[i].down.y=y2;
        }
        Point p;
        memset(num,0,sizeof num);
        while(m--){
            scanf("%d%d",&p.x,&p.y);
            BinSearch(p);
        }
        for(int i=0;i<=n;i++){
            printf("%d: %d\n",i,num[i]);
        }
        puts("");
    }
}

POJ 2398 Toy Storage

分析：和上一题差不多，就是多了一步排序，多加一个数组。

#include<iostream>
#include<cstdio>
#include<iomanip>
#include<cstring>
#include<vector>
#include<map>
#include<queue>
#include<set>
#include<algorithm>
#include<cmath>
using namespace std;
const int MAXN=5000+10;
int sgn(int x){
    if(x==0) return 0;
    if(x<0) return -1;
    else return 1;
}
struct Point{
    int x,y;
    Point(){}
    Point(int x,int y):x(x),y(y){}
    bool operator < (const Point& b)const{
        if(x!=b.x) return x<b.x;
        return y<b.y;
    }
    Point operator-(const Point& b)const{
        return Point(x-b.x,y-b.y);
    }
    //叉积
    int operator ^(const Point &b)const{
        return x*b.y-y*b.x;
    } 
};
int n,m;
struct Line{
    Point up,down;
    Line(){}
    Line(Point up,Point down):up(up),down(down){}
    bool operator <(const Line& x)const{
        return up<x.up;
    }
}box[MAXN];
int num[MAXN],cnt[MAXN];
void BinSearch(Point p){
    int L=0,R=n+1,ans;
    while(L<=R){
        int mid=L+((R-L)>>1);
        if(sgn((box[mid].up-p)^(box[mid].down-p))<0){
            ans=mid;
            R=mid-1;
        }else{
            L=mid+1;
        }
    }
    num[ans-1]++;
}
int main(){
    while(~scanf("%d",&n)&&n){
        int x1,y1,x2,y2,x,y;
        scanf("%d%d%d%d%d",&m,&x1,&y1,&x2,&y2);
        box[0]=Line(Point(x1,y1),Point(x1,y2));
        box[n+1]=Line(Point(x2,y1),Point(x2,y2));
        for(int i=1;i<=n;i++){
            scanf("%d%d",&box[i].up.x,&box[i].down.x);
            box[i].up.y=y1; box[i].down.y=y2;
        }
        sort(box,box+n+2);
        Point p;
        memset(num,0,sizeof num);
        memset(cnt,0,sizeof cnt);
        for(int i=0;i<m;i++){
            scanf("%d%d",&p.x,&p.y);
            BinSearch(p);
        }
        puts("Box");
        for(int i=0;i<=n;i++){
            if(num[i]!=0) cnt[num[i]]++;
        }
        for(int i=1;i<=m;i++){
            if(cnt[i]!=0) printf("%d: %d\n",i,cnt[i]);
        }
    }
}

POJ 3304 Segments

分析：这题就是问是否存在一条直线，使得所有线段在这条直线上的投影存在至少一个公共点。

显然，投影在直线存在公共点，那么以公共点为垂足的这个直线的垂线肯定穿过所有线段，这个问题就转化为了是否存在一条直线和所有线段相交。那么枚举所有线段的端点任取两个作为直线就行了（可以自己画图看一下）。

有一点需要注意：在枚举端点时，如果两个端点的距离小于1e-8就跳过去，因为在题目要求精度下，相当于零向量和其他向量叉积，这样的叉积出来就是0，算出来的结果肯定就错了。

#include<iostream>
#include<cstdio>
#include<iomanip>
#include<cstring>
#include<vector>
#include<map>
#include<queue>
#include<set>
#include<algorithm>
#include<cmath>
using namespace std;
const double eps=1e-8;
const int MAXN=100+10;
int t,n;
int sgn(double x){
    if(fabs(x)<eps) return 0;
    return x<0?-1:1;
}
struct Point {
    double x,y;
    Point(){}
    Point(double x,double y):x(x),y(y){}
    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;
    }
}P[MAXN<<1];
struct Line{
    Point s,e;
    Line(){}
    Line(Point _s,Point _e):s(_s),e(_e){}
}S[MAXN];
int ok(Point a,Point b,Point c){
    return sgn((a^b)*(a^c));
}
bool dis(Point a,Point b){
    return sgn(sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)));
}
bool check(Point a,Point b){
    for(int i=0;i<n;i++){
        int ret=ok(b-a,S[i].s-a,S[i].e-a);
        if(ret<=0) continue;
        return 0;
    }
    return 1;
}
int main(){
    scanf("%d",&t);
    double x1,y1,x2,y2;
    while(t--){
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            scanf("%lf%lf%lf%lf",&P[i<<1].x,&P[i<<1].y,&P[i<<1|1].x,&P[i<<1|1].y);
            S[i]=Line(P[i<<1],P[i<<1|1]);
        }
        if(n==1||n==2){
            puts("Yes!");
            continue;
        }
        int flag=0;
        for(int i=0;i<(n<<1);i++){
            if(flag) break;
            for(int j=i+1;j<(n<<1);j++){
                if(dis(P[i],P[j])&&check(P[i],P[j])){
                    flag=1;
                    break;
                }
            }
        }
        if(flag) puts("Yes!");
        else puts("No!");
    }
    return 0;
}

POJ 1269 Intersecting Lines

分析：就是让求两个直线的交点，叉积判断平行和三点共线，利用直线的参数表示法求解交点。

注意⚠️：如果使用%.2lf用C++提交，%.2f用G++提交。

#include<iostream>
#include<cstdio>
#include<iomanip>
#include<cstring>
#include<vector>
#include<map>
#include<queue>
#include<set>
#include<algorithm>
#include<cmath>
using namespace std;
const double eps=1e-8;
int sgn(double x){
    if(fabs(x)<eps) return 0;
    return x<0?-1:1;
}
struct Point{
    double x,y;
    Point(){}
    Point(double _x,double _y):x(_x),y(_y){}
    Point operator -(const Point& b)const{
        return Point(x-b.x,y-b.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);
    }
    //叉积
    double operator ^(const Point& b)const{
        return x*b.y-y*b.x;
    }
};
struct Line{
    Point s,e;
    Line(){}
    Line(Point _s,Point _e):s(_s),e(_e){}
    //点和直线的关系
    //1 在左侧
    //2 在右侧
    //3 在直线上
    int relation(Point p){
        int c=sgn((p-s)^(e-s));
        if(c<0) return 1;
        else if(c>0) return 2;
        else return 3;
    }
    //两向量平行
    bool parallel(Line v){
        return sgn((e-s)^(v.e-v.s))==0;
    }
    //两直线关系
    //0 平行
    //1 重合
    //2 相交
    int linecrossline(Line v){
        if((*this).parallel(v)) return v.relation(s)==3;
        return 2;
    }
    //求两直线的交点
    //要保证两直线不平行或重合
    Point crosspoint(Line L){
        Point P=s,Q=L.s,v=e-s,w=L.e-L.s;
        Point u=P-Q;
        double t=(w^u)/(v^w);
        return P+v*t;
    }
};
int main(){
    int t;
    scanf("%d",&t);
    puts("INTERSECTING LINES OUTPUT");
    Line A,B;
    while(t--){
        scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&A.s.x,&A.s.y,&A.e.x,&A.e.y,&B.s.x,&B.s.y,&B.e.x,&B.e.y);
        int re=A.linecrossline(B);
        if(re==0) puts("NONE");
        else if(re==1) puts("LINE");
        else{
            printf("POINT ");
            Point itsct=A.crosspoint(B);
            printf("%.2lf %.2lf\n",itsct.x,itsct.y);
        }
    }
    puts("END OF OUTPUT");
}

POJ 1556 The Doors

分析：就是一个房间有很多墙，让你求两个坐标之间的最短路。直接根据两点之间是否有墙建图（判断线段是否规范相交），然后跑个最短路。

#include<iostream>
#include<cstdio>
#include<iomanip>
#include<cstring>
#include<vector>
#include<map>
#include<queue>
#include<set>
#include<algorithm>
#include<cmath>
using namespace std;
const double eps=1e-8;
const int maxn=(74<<1)+10;
const double INF=1e9;
int sgn(double x){
    if(fabs(x)<eps) return 0;
    return x<0?-1:1;
}
int n;
struct Point{
    double x,y;
    Point(){}
    Point(double _x,double _y):x(_x),y(_y){}
    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;
    }
}P[maxn];
struct Line{
    Point s,e;
    Line(){}
    Line(Point _s,Point _e):s(_s),e(_e){}
    //两线段相交判断
    //2 规范相交
    //1 非规范相交
    //0 不相交
    int segcrossseg(Line v){
        int d1=sgn((e-s)^(v.s-s));
        int d2=sgn((e-s)^(v.e-s));
        int d3=sgn((v.e-v.s)^(s-v.s));
        int d4=sgn((v.e-v.s)^(e-v.s));
        if((d1^d2)==-2 && (d3^d4)==-2) return 2;
        return (d1==0 && sgn((v.s-s)*(v.s-e))<=0)||
                (d2==0 && sgn((v.e-s)*(v.e-e))<=0)||
                (d3==0 && sgn((s-v.s)*(s-v.e))<=0)||
                (d4==0 && sgn((e-v.s)*(e-v.e))<=0);
    }
}L[maxn];
int cntP,cntL;

double G[maxn][maxn],dis[maxn];
int vis[maxn];
int s,t;
double PPdis(Point a,Point b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int main(){
    while(~scanf("%d",&n)&&n!=-1){
        cntP=0;cntL=0;
        double x,y1,y2,y3,y4;
        P[cntP++]=Point(0,5);
        for(int i=0;i<n;i++){
            scanf("%lf%lf%lf%lf%lf",&x,&y1,&y2,&y3,&y4);
            P[cntP++]=Point(x,y1);P[cntP++]=Point(x,y2);
            P[cntP++]=Point(x,y3);P[cntP++]=Point(x,y4);
            L[cntL++]=Line(Point(x,0),Point(x,y1));
            L[cntL++]=Line(Point(x,y2),Point(x,y3));
            L[cntL++]=Line(Point(x,y4),Point(x,10));
        }
        P[cntP++]=Point(10,5);
        for(int i=0;i<cntP;i++){
            for(int j=0;j<cntP;j++){
                G[i][j]=(i==j?0:INF);
            }
        }
        //建图
        for(int i=0;i<cntP;i++){
            for(int j=i+1;j<cntP;j++){
                int flag=1;
                for(int k=0;k<cntL;k++){
                    if(sgn(L[k].s.x-P[j].x)>0) break;
                    if(P[i].x!=P[j].x&&Line(P[i],P[j]).segcrossseg(L[k])!=2){
                        continue;
                    }else{
                        flag=0;
                        break;
                    }
                }
                if(flag){
                    G[i][j]=G[j][i]=PPdis(P[i],P[j]);
                }
            }
        }
        for(int i=0;i<cntP;i++){
            dis[i]=INF;vis[i]=0;
        }
        dis[0]=0;
        for(int i=0;i<cntP;i++){
            int k=-1;
            double Min=INF;
            for(int j=0;j<cntP;j++){
                if(!vis[j]&&sgn(dis[j]-Min)<0){
                    Min=dis[j];
                    k=j;
                }
            }
            if(k==-1) break;
            vis[k]=true;
            for(int j=0;j<cntP;j++){
                if(!vis[j]&&sgn(dis[k]+G[k][j]-dis[j])<0){
                    dis[j]=dis[k]+G[k][j];
                }
            }
        }
        printf("%.2lf\n",dis[cntP-1]);
    }
    return 0;
}

POJ 2653 Pick-up sticks

分析：直接从前往后暴力判断。

#include<iostream>
#include<cstdio>
#include<iomanip>
#include<cstring>
#include<vector>
#include<map>
#include<queue>
#include<set>
#include<algorithm>
#include<cmath>
using namespace std;
const double eps=1e-8;
const int maxn=1e5+10;
int sgn(double x){
    if(fabs(x)<eps) return 0;
    return x<0?-1:1;
}
struct Point{
    double x,y;
    Point(){}
    Point(double _x,double _y):x(_x),y(_y){}
    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;
    }
};
struct Line{
    Point s,e;
    Line(){}
    Line(Point _s,Point _e):s(_s),e(_e){}
    //两线段相交判断
    //2 规范相交
    //1 非规范相交
    //0 不相交
    int segcrossseg(Line v){
        int d1=sgn((e-s)^(v.s-s));
        int d2=sgn((e-s)^(v.e-s));
        int d3=sgn((v.e-v.s)^(s-v.s));
        int d4=sgn((v.e-v.s)^(e-v.s));
        if((d1^d2)==-2 && (d3^d4)==-2) return 2;
        return (d1==0 && sgn((v.s-s)*(v.s-e))<=0)||
                (d2==0 && sgn((v.e-s)*(v.e-e))<=0)||
                (d3==0 && sgn((s-v.s)*(s-v.e))<=0)||
                (d4==0 && sgn((e-v.s)*(e-v.e))<=0);
    }
}L[maxn];
int main(){
    int n;
    while(~scanf("%d",&n)&&n){
        for(int i=1;i<=n;i++){
            scanf("%lf%lf%lf%lf",&L[i].s.x,&L[i].s.y,&L[i].e.x,&L[i].e.y);
        }
        int f=0;
        printf("Top sticks: ");
        for(int i=1;i<=n;i++){
            int j=i+1;
            for(;j<=n;j++){
                if(L[i].segcrossseg(L[j])==2) break;
            }
            if(j==n+1){
                if(f!=0) printf(", ");
                printf("%d",i);
                f=1;
            }
            
        }
        puts(".");
    }
    return 0;
}

POJ 1066 Treasure Hunt

分析：就是判断最少经过几个墙到达藏宝室。还是线段相交问题。
注意⚠️：n=0时直接输出1就行。

#include<iostream>
#include<cstdio>
#include<iomanip>
#include<cstring>
#include<vector>
#include<map>
#include<queue>
#include<set>
#include<algorithm>
#include<cmath>
using namespace std;
const double eps=1e-8;
const int INF=0x3f3f3f3f;
const int maxn=30+10;
int sgn(double x){
    if(fabs(x)<eps) return 0;
    return x<0?-1:1;
}
struct Point{
    double x,y;
    Point(){}
    Point(double _x,double _y):x(_x),y(_y){}
    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;
    }
}P[maxn<<1];
struct Line{
    Point s,e;
    Line(){}
    Line(Point _s,Point _e):s(_s),e(_e){}
    //两线段相交判断
    //2 规范相交
    //1 非规范相交
    //0 不相交
    int segcrossseg(Line v){
        int d1=sgn((e-s)^(v.s-s));
        int d2=sgn((e-s)^(v.e-s));
        int d3=sgn((v.e-v.s)^(s-v.s));
        int d4=sgn((v.e-v.s)^(e-v.s));
        if((d1^d2)==-2 && (d3^d4)==-2) return 2;
        return (d1==0 && sgn((v.s-s)*(v.s-e))<=0)||
                (d2==0 && sgn((v.e-s)*(v.e-e))<=0)||
                (d3==0 && sgn((s-v.s)*(s-v.e))<=0)||
                (d4==0 && sgn((e-v.s)*(e-v.e))<=0);
    }
}L[maxn];
int main(){
    int n;
    scanf("%d",&n);
    if(n==0){
        printf("Number of doors = 1");
        return 0;
    }
    for(int i=0;i<n;i++){
        scanf("%lf%lf%lf%lf",&P[i<<1].x,&P[i<<1].y,&P[i<<1|1].x,&P[i<<1|1].y);
        L[i]=Line(P[i<<1],P[i<<1|1]);
    }
    Point p;
    scanf("%lf%lf",&p.x,&p.y);
    int ans=INF;
    for(int i=0;i<(n<<1);i++){
        Line cur=Line(P[i],p);
        int cnt=0;
        for(int j=0;j<n;j++){
            cnt+=(cur.segcrossseg(L[j])==2);
        }
        ans=min(ans,cnt);
    }
    printf("Number of doors = %d",ans+1);
    return 0;
}

POJ 1410 Intersection

分析：可以直接判断线段相交+线段在矩形内，也可以判断投影+点的位置关系，还可以利用计算机图形学中的剪裁算法等。
若线段和矩形未通过快速排斥试验(Quick Rejection Test)**，则两者不可能相交。
反之，在通过QRT后，线段所在矩形一定与矩形有公共部分。
此时若线段所在直线与矩形任一对角线**相交，则线段一定与矩形区域相交。

#include<iostream>
#include<cstdio>
#include<iomanip>
#include<cstring>
#include<vector>
#include<map>
#include<queue>
#include<set>
#include<algorithm>
#include<cmath>
using namespace std;
struct Point{
    double x,y;
    Point(){}
    Point(double _x,double _y):x(_x),y(_y){}
    Point operator -(const Point& b)const{
        return Point(x-b.x,y-b.y);
    }
}s,e,l,r;
inline double Cross(const Point a,const Point b){
    return a.x*b.y-a.y*b.x;
}
inline bool seg_intersection_rect(){
    if(min(s.x,e.x)<=max(l.x,r.x)&&max(s.x,e.x)>=min(l.x,r.x)&&
        min(s.y,e.y)<=max(l.y,r.y)&&max(s.y,e.y)>=min(l.y,r.y)&&
        (Cross(e-s,l-s)*Cross(e-s,r-s)<=0||
        Cross(e-s,Point(l.x,r.y)-s)*Cross(e-s,Point(r.x,l.y)-s)<=0))return 1;
    return 0;
}

int main(){
    int n;
    scanf("%d",&n);
    while(n--){
        scanf("%lf%lf%lf%lf",&s.x,&s.y,&e.x,&e.y);
        scanf("%lf%lf%lf%lf",&l.x,&l.y,&r.x,&r.y);
        if(seg_intersection_rect()){
            puts("T");
        }else puts("F");
    }
    return 0;
}

POJ 1696 Space Ant

分析：由于数据较少，直接按照极角进行排序，反复找相对当前点极角最小的点。

#include<iostream>
#include<cstdio>
#include<iomanip>
#include<cstring>
#include<vector>
#include<map>
#include<queue>
#include<set>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=50+10;
struct Point{
    int x,y;
    int id;
    Point(){}
    Point(int _x,int _y):x(_x),y(_y){}
    Point operator -(const Point& b)const{
        return Point(x-b.x,y-b.y);
    }
    int operator ^(const Point& b)const{
        return x*b.y-y*b.x;
    }
}P[maxn],ans[maxn];
int cur=0,cnt=0;
int dis2(Point a,Point b){
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
bool cmp(Point a,Point b){
    int temp=(a-P[cur])^(b-P[cur]);
    if(temp>0) return true;
    else if(temp==0&&dis2(P[cur],a)<dis2(P[cur],b)) return true;
    else return false;
}
int main(){
    int M,N;
    scanf("%d",&M);
    while(M--){
        scanf("%d",&N);
        for(int i=0;i<N;i++){
            scanf("%d%d%d",&P[i].id,&P[i].x,&P[i].y);
            if(P[i].y<P[0].y) swap(P[0],P[i]);
        }
        cur=0;cnt=0;
        for(int i=0;i<N;i++){
            sort(P+cur,P+N,cmp);
            ans[cur++]=P[cnt++];
        }
        printf("%d",N);
        for(int i=0;i<N;i++){
            printf(" %d",ans[i].id);
        }
        puts("");
    }
    return 0;
}

POJ 3347 Kadj Squares

分析：首先计算出每个正方形的左边和右边顶点的横坐标，怎么求哪？就是枚举每个正方形前面的正方形，让当前的与前面的每个都算出一个正好贴紧的情况，其中只有一个是合法的（和其他的不相交的），就是那个横坐标最大的，所以每次求 $max$ 就行了，最后就是收缩被覆盖的正方形坐标，如果两个相邻的正方形大小不同，那么肯定存在覆盖关系，详细见图下代码：

#include <iostream>
#include <cstdio>
#include <iomanip>
#include <cstring>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <cmath>
#include <bitset>
using namespace std;
#define LL long long
const int maxn = 50+10;
const double eps = 1e-8;
const double sqrt2 = sqrt(2.0);
int n;
struct Squ{
    double left, right, len;
}S[maxn];
int sgn(double x){
    if(fabs(x) < eps) return 0;
    if(x<0) return -1;
    else return 1;
}
int main(){
    while(scanf("%d", &n)!=EOF && n){
        int cur_right=0, cur_side=0;
        for(int i=0; i<n; ++i){
            scanf("%lf", &S[i].len); 
        }
        for(int i=0; i<n; ++i){
            double L = 0;
            for(int j=0; j<i; ++j){
                L = max(L, S[j].right-fabs(S[j].len-S[i].len)/sqrt2);
            }
            S[i].left=L;
            S[i].right=S[i].left+S[i].len*sqrt2;
        }
        for(int i=0; i<n; ++i){
            for(int j=0; j<i; ++j){
                if(sgn(S[i].len-S[j].len)==1 && sgn(S[i].left-S[j].right)==-1){
                    S[j].right = S[i].left;
                }
                if(sgn(S[i].len-S[j].len)==-1 && sgn(S[i].left-S[j].right)==-1){
                    S[i].left = S[j].right;
                }
            }
        }
        for(int i=0; i<n; ++i){
            if(sgn(S[i].right-S[i].left)==1) printf("%d ", i+1);
        }
        puts("");
    }
    return 0;
}

POJ 2826 An Easy Problem?!

分析：被这题坑了好久啊，还是经验少，注意一下坑点：

1. 特判平行（一般都能想到，但是我就是wa​在了这点）
2. 在利用斜率计算线上点时注意斜率不存在的情况。
3. 相交却装不了水有三种情况，详见代码
4. 还有个(sgn(p1.y-cp.y)==0&&(p1.x-cp.x)==0)||(sgn(p3.y-cp.y)==0&&(p3.x-cp.x)==0)

可能分析麻烦了，不过总算是过了。

#include <iostream>
#include <cstdio>
#include <iomanip>
#include <cstring>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <complex>
using namespace std;
const double eps = 1e-8;
int sgn(double x){
    if(fabs(x) < eps) return 0;
    if(x < 0) return -1;
    else return 1;
}
struct Point{
    double x,y;
    Point(){}
    Point(double _x, double _y){
        x = _x;
        y = _y;
    }
    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;
    }
};
struct Line{
    Point s, e;
    Line(){}
    Line(Point _s, Point _e){
        s = _s;
        e = _e;
    }
    //两向量平行 (对应直线平行或重合)
    bool parallel(Line v){
        return sgn((e-s)^(v.e-v.s)) == 0;
    }
    //两线段相交判断
    //2 规范相交
    //1 非规范相交
    //0 不相交
    int segcrossseg(Line v){
        int d1 = sgn((e-s)^(v.s-s));
        int d2 = sgn((e-s)^(v.e-s));
        int d3 = sgn((v.e-v.s)^(s-v.s));
        int d4 = sgn((v.e-v.s)^(e-v.s));
        if( (d1^d2)==-2 && (d3^d4)==-2 )return 2;
        return (d1==0 && sgn((v.s-s)*(v.s-e))<=0) ||
        (d2==0 && sgn((v.e-s)*(v.e-e))<=0) ||
        (d3==0 && sgn((s-v.s)*(s-v.e))<=0) ||
        (d4==0 && sgn((e-v.s)*(e-v.e))<=0);
    }
    //求两直线的交点
    //要保证两直线不平行或重合
    Point crosspoint(Line v){
        double a1 = (v.e-v.s)^(s-v.s);
        double a2 = (v.e-v.s)^(e-v.s);
        return Point((s.x*a2-e.x*a1)/(a2-a1),(s.y*a2-e.y*a1)/(a2-a1
        ));
    }
};
int main(){
    int n;
    double x1,x2,x3,x4,y1,y2,y3,y4;
    cin>>n;
    while(n--){
        cin>>x1>>y1>>x2>>y2>>x3>>y3>>x4>>y4;
        Point p1=Point(x1,y1), p2=Point(x2,y2);
        Point p3=Point(x3,y3), p4=Point(x4,y4);
        Line l1=Line(p1,p2), l2=Line(p3,p4);
        if(l1.parallel(l2)){
            cout<<"0.00\n";
        }else if(l1.segcrossseg(l2)){//判断相交
            if(sgn(y1-y2)==0||sgn(y3-y4)==0){//判断是否存在水平线段
                cout<<"0.00\n";
            }else{
                Point cp = l1.crosspoint(l2);
                Point unit_row=Point(1,0);
                if(sgn(p1.y-p2.y)<0) swap(p1,p2);//令p1是第一个线段y值偏大那个点
                if(sgn(p3.y-p4.y)<0) swap(p3,p4);//令p3是第二个线段y值偏大那个点
                if((sgn(p1.y-cp.y)==0&&(p1.x-cp.x)==0)||(sgn(p3.y-cp.y)==0&&(p3.x-cp.x)==0)){
                    cout<<"0.00\n";
                }else if(sgn((p1-cp)*unit_row)==1&&sgn((p3-cp)*unit_row)==1 &&
                 ((sgn(p1.x-p3.x)>=0&&sgn(p1.y-p3.y)>=0&&((p3-cp)^(p1-cp))>=0)
                 ||(sgn(p1.x-p3.x)<=0&&sgn(p1.y-p3.y)<=0&&((p1-cp)^(p3-cp))>=0))){//all_right
                    cout<<"0.00\n";
                }else if(sgn((p1-cp)*unit_row)==-1&&sgn((p3-cp)*unit_row)==-1 
                && ((sgn(p1.x-p3.x)>=0&&sgn(p1.y-p3.y)<=0&&((p3-cp)^(p1-cp))>=0)
                ||(sgn(p1.x-p3.x)<=0&&sgn(p1.y-p3.y)>=0&&((p1-cp)^(p3-cp))>=0))){//all_left
                    cout<<"0.00\n";
                }else{
                    //cp p1 p3
                    double k = 1.0;
                    if(sgn(p1.y-p3.y)<=0){
                        if(p3.x==cp.x){//如果不存在斜率
                            p3.y = p1.y; 
                            p3.x = cp.x;
                        }else{
                            k = (p3.y-cp.y)/(p3.x-cp.x);
                            p3.y = p1.y; 
                            p3.x = (p3.y-cp.y)/k + cp.x;
                        }
                    }else {
                        if(p1.x==cp.x){
                            p1.y = p3.y; 
                            p1.x = cp.x;
                        }else{
                            k = (p1.y-cp.y)/(p1.x-cp.x);
                            p1.y = p3.y; 
                            p1.x = (p1.y-cp.y)/k + cp.x;
                        }
                    }
                    double ans = fabs((p1-cp)^(p3-cp))/2;
                    cout<<fixed<<setprecision(2)<<ans<<endl;
                }
            }
        }else{
            cout<<"0.00\n";
        }
    }
    return 0;
}

POJ 1039 Pipe

POJ 3449 Geometric Shapes

POJ 1584 A Round Peg in a Ground Hole