Algoogle

Algorithm for Programming Contest

PKU 3668 Game of Lines

Category: PKU Tag: geometry

Game of Lines

問題概要


解法


すべての組み合わせを試せば良い.
傾きはintのpairを(dx, dy)で持っておく. (dxは非負)
それらは既約もしくは(0, 0), (0, 1)に正規化する.

コード


(3668.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 <algorithm>
#include <cstdio>
#include <set>
#include <map>

using namespace std;

typedef pair<int,int> pii;

int N;
pii dots[256];

int main(){
    scanf("%d", &N);

    for(int i = 0; i < N; i++){
        int x, y; scanf("%d%d", &x, &y);
        dots[i] = pii(x, y);
    }

    set<pii> args;

    for(int i = 0; i < N; i++)
        for(int j = 0; j < i; j++){
            int dx = dots[i].first - dots[j].first;
            int dy = dots[i].second - dots[j].second;
            if(dy == 0) args.insert(pii(0,0));
            else if(dx == 0) args.insert(pii(0,1));
            else {
                int g = __gcd(dx, dy);
                dx /= g; dy /= g;
                if(dx < 0){
                    dx *= -1;
                    dy *= -1;
                }
                args.insert(pii(dx, dy));
            }
        }
    printf("%d\n", int(args.size()));
    return 0;
}

Comments