解題區/解題區 - UVa

UVa 11123 - Counting Trapizoid

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

給平面上 N 個不重複的點，有多少梯形可以由這幾個點構成？

  • 有四條邊
  • 一對平行、一對不平行
  • 面積為正

Sample Input

1
2
3
4
5
6
7
8
9
10
11
4
0 0
1 0
0 1
1 1
4
0 0
1 1
2 0
0 1
0

Sample Output

1
2
Case 1: 0
Case 2: 1

Solution

先窮舉任兩個點拉起的線段 (let N = n*(n-1)/2)。

針對線段斜率排序，接著將相同斜率放置在同一個 group。

對於每一個 group 的每一個元素計算有多少可以配對成梯形。

  • 防止共線
  • 防止線段具有相同長度 (防止兩對邊平行)

斜率相同，按照交 y 軸的大小由小到大排序。(左側到右側)，由左側掃描到右側，依序把非共線的線段丟入，並且紀錄線段長度資訊。每一個能匹配的組合為 當前線段數 - 相同長度線段數。

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
135
136
137
138
139
#include <stdio.h> 
#include <math.h>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <assert.h>
using namespace std;
#define eps 1e-9
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}	
    Pt operator-(const Pt &a) const {
        return Pt(x - a.x, y - a.y);
    }
    Pt operator+(const Pt &a) const {
        return Pt(x + a.x, y + a.y);
    }
    bool operator<(const Pt &a) const {
        if (fabs(x - a.x) > eps)
            return x < a.x;
        if (fabs(y - a.y) > eps)
            return y < a.y;
        return false;
    }
};
double dist(Pt a, Pt b) {
    return hypot(a.x - b.x, a.y - b.y);
}
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
double cross(Pt o, Pt a, Pt b) {
    return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
int between(Pt a, Pt b, Pt c) {
    return dot(c - a, b - a) >= -eps && dot(c - b, a - b) >= -eps;
}
int onSeg(Pt a, Pt b, Pt c) {
    return between(a, b, c) && fabs(cross(a, b, c)) < eps;
}
struct Seg {
    Pt s, e;
    double angle;
    int label;
    Seg(Pt a = Pt(), Pt b = Pt(), int l=0):s(a), e(b), label(l) {
        angle = atan2(e.y - s.y, e.x - s.x);
    }
    bool operator<(const Seg &other) const {
        if (fabs(angle - other.angle) > eps)
            return angle > other.angle;
        if (cross(other.s, other.e, s) > eps)
            return true;
        return false;
    }
};
struct DOUBLE {
    double v;
    DOUBLE(double a = 0):
        v(a) {}
    bool operator<(const DOUBLE &other) const {
        if (fabs(v - other.v) > eps)
            return v < other.v;
        return false;
    }
};
Pt D[256];
Seg segs[65536], buf[65536];
int main() {
    int cases = 0;
    int n, m;
    while (scanf("%d", &n) == 1 && n) {
        for (int i = 0; i < n; i++)
            scanf("%lf %lf", &D[i].x, &D[i].y);
        sort(D, D + n);
        
        m = 0;
        for (int i = 0; i < n; i++)
            for (int j = i+1; j < n; j++)
                segs[m++] = Seg(D[i], D[j]);
        
        sort(segs, segs + m);
        long long ret = 0;
        for (int i = 0; i < m; ) {
            int j = i, tn = 0;
            while (j < m && fabs(segs[i].angle - segs[j].angle) < eps)
                buf[tn++] = segs[j], j++;
            i = j;
            
            map<DOUBLE, int> LEN; // LEN[len] = count.
            queue<Seg> Q;
            int tmp = 0;
//			for (int k = 0; k < tn; k++)
//				printf("(%lf %lf) - (%lf %lf)\n", buf[k].s.x, buf[k].s.y, buf[k].e.x, buf[k].e.y);
//			puts("--- same slope");
            for (int k = 0; k < tn; k++) {
                while (!Q.empty() && fabs(cross(buf[k].s, buf[k].e, Q.front().s)) > eps) {
                    Seg t = Q.front();
                    Q.pop();
                    tmp++, LEN[DOUBLE(dist(t.s, t.e))]++;
                }
                int comb = tmp - LEN[DOUBLE(dist(buf[k].s, buf[k].e))]; // remove same length
                ret += comb;
                Q.push(buf[k]);
            }
        }
        printf("Case %d: %lld\n", ++cases, ret);
    }
    return 0;
}
/*
4
0 0
1 0
0 1
1 1
4
0 0
1 1
2 0
0 1
6
5 1
3 1
5 0
3 3
2 4
0 8
0
*/