Algoogle

Algorithm for Programming Contest

PKU 3274 Alignment of the Planets

Category: PKU Tag: geometry

Alignment of the Planets

問題概要


解法


座標はすべて整数で与えられるので有理数クラスを作って傾きを比較すれば正確に比較できる.
あとは3重ループでまわす.

コード


(3274.cpp) download
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
#include <cstdio>
#include <map>
#include <vector>

using namespace std;
typedef pair<int,int> pii;
struct points{
    int x, y, z;
    points(int x, int y, int z):x(x),y(y),z(z){}
};

struct frac{
    int num, den;
    frac(int num, int den):num(num),den(den){}
    bool operator==(const frac &f) const{
        return num * f.den == den * f.num;
    }
};

int N;
pii p[1024];

int main(){
    scanf("%d", &N);
    for(int i = 0; i < N; i++)
        scanf("%d%d", &p[i].first, &p[i].second);

    vector<points> ans;

    for(int i = 0; i < N; i++)
        for(int j = i+1; j < N; j++)
            for(int k = j+1; k < N; k++){
                frac a = frac(p[j].second-p[i].second, p[j].first-p[i].first);
                frac b = frac(p[k].second-p[i].second, p[k].first-p[i].first);
                if(a == b) ans.push_back(points(i+1,j+1,k+1));
            }
    printf("%d\n", (int)ans.size());
    for(int i = 0; i < (int)ans.size(); i++)
        printf("%d %d %d\n", ans[i].x, ans[i].y, ans[i].z);
    return 0;
}

Comments