解題區/解題區 - UVa

UVa 979 - The Abominable Triangleman

contents

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

Problem

簡化版本的 UVA 10206 - Stars，這一題只求三角形之間的情況，並且只需要考慮相同大小、可能會任意地旋轉或者是翻轉 (鏡射)。

找到一個解輸出即可。

Sample Input

1
2
3
4
5
6
7
8
9
10
5 15
8 5
20 10
6
5 17
5 20
20 5
10 5
15 20
15 10

Sample Output

1
2
3
5 17
10 5
15 20

Solution

窮舉一條三角形上的邊當作 AB 邊，利用向量旋轉找到 C 點位置，查閱 C 點位置是否有存在於輸入的點集合中。

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
140
#include <stdio.h> 
#include <stdio.h> 
#include <math.h>
#include <string.h>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
#define eps 1e-6
struct Pt {
    double x, y;
    Pt(double a = 0, double b = 0):
    	x(a), y(b) {}
    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;
    }
    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);
    }
    Pt operator/(const double a) const {
        return Pt(x /a, y /a);
    }
    Pt operator*(const double a) const {
        return Pt(x *a, y *a);
    }
    int in() {
    	return scanf("%lf %lf", &x, &y) == 2;
    }
};
double dist(Pt a, Pt b) {
    return hypot(a.x - b.x, a.y - b.y);
}
double dist2(Pt a, Pt b) {
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
double length(Pt a) {
    return hypot(a.x, a.y);
}
double dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y;
}
double cross2(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x;
}
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);
}
double angle(Pt a, Pt b) {
    return acos(dot(a, b) / length(a) / length(b));
}
Pt rotateRadian(Pt a, double radian) {
    double x, y;
    x = a.x * cos(radian) - a.y * sin(radian);
    y = a.x * sin(radian) + a.y * cos(radian);
    return Pt(x, y);
}
int main() {
    Pt A, B, C, D[2048];
    int N, cases = 0;
    while(A.in() && B.in() && C.in()) {
        scanf("%d", &N);
        set<Pt> S;
        for(int i = 0; i < N; i++)
            D[i].in(), S.insert(D[i]);
        if(cases++)	puts("");
        double AB = dist2(A, B), BC = dist2(B, C), sqrAB = dist(A, B), sqrBC = dist(B, C);
        double aABC = angle(A - B, C - B);
        sort(D, D + N);
        
        vector<Pt> ret;
        for(int i = 0; i < N; i++) {
            for(int j = i+1; j < N; j++) {
                if(AB < (D[j].x - D[i].x) * (D[j].x - D[i].x))
                    break;
                if(fabs(AB - dist2(D[i], D[j])) < eps) {
//					printf("%lf %lf %lf %lf\n", D[i].x, D[i].y, D[j].x, D[j].y);
                    Pt vBC, tc;
                    vBC = rotateRadian(D[i] - D[j], +aABC) * (sqrBC/sqrAB);
                    tc = D[j] + vBC;
                    if(S.find(tc) != S.end()) {
                        ret.push_back(tc);
                        ret.push_back(D[i]);
                        ret.push_back(D[j]);
                    }
                    
                    vBC = rotateRadian(D[i] - D[j], -aABC) * (sqrBC/sqrAB);
                    tc = D[j] + vBC;
                    if(S.find(tc) != S.end()) {
                        ret.push_back(tc);
                        ret.push_back(D[i]);
                        ret.push_back(D[j]);
                    }					
                    
                    vBC = rotateRadian(D[j] - D[i], +aABC) * (sqrBC/sqrAB);
                    tc = D[i] + vBC;
                    if(S.find(tc) != S.end()) {
                        ret.push_back(tc);
                        ret.push_back(D[i]);
                        ret.push_back(D[j]);
                    }
                    
                    vBC = rotateRadian(D[j] - D[i], -aABC) * (sqrBC/sqrAB);
                    tc = D[i] + vBC;
                    if(S.find(tc) != S.end()) {
                        ret.push_back(tc);
                        ret.push_back(D[i]);
                        ret.push_back(D[j]);
                    }
                }
            }
        }
        if(ret.size()) {
            sort(ret.begin(), ret.end());
            for(int i = 0; i < 3; i++) {
                printf("%.0lf %.0lf\n", ret[i].x, ret[i].y);
            }
        }
    }
    return 0;
}
/*
5 15
8 5
20 10
6
5 17
5 20
20 5
10 5
15 20
15 10
*/