专题十三 基础计算几何 | 李博的博客
0%

专题十三 基础计算几何

发表于 更新于 分类于 阅读次数： Valine：

POJ 2318 TOYS

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#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，算出来的结果肯定就错了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#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++提交。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#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就行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#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后，线段所在矩形一定与矩形有公共部分。
此时若线段所在直线与矩形任一对角线相交，则线段一定与矩形区域相交。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#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$ 就行了，最后就是收缩被覆盖的正方形坐标，如果两个相邻的正方形大小不同，那么肯定存在覆盖关系，详细见图下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#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?!

poj-2826-status

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

  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)

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#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

如果对您有帮助，请我喝杯奶茶？