본문 바로가기

알고리즘 관련/UVaOJ

UVaOJ)12159 Gun Fight

문제:https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=3311


N개의 power가 존재하는 점이 주어지고 진영을 가르는 직선을 결정하는 두 점이 주어진다.


두 점으로 부터 진영을 갈라서 수가 적은 진영이 수가 많은 진영을 이기도록 최대한 매칭할 수 있는 수를 출력하는 문제이다.


ccw를 이요하여 모든 점의 진영을 구해준 뒤 진영이 적은 쪽에서 진영이 많은 쪽으로 두 점 사이의 거리가 R이하이고 Power가 0이상이고 진영이 적은 쪽의 power가 진영이 많은쪽의 power보다 많은 두 점을 서로 매칭시켜준 뒤 최대매칭을 구해주면 된다.


 

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
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
using namespace std;
int n, x, y, p, a, b, cnt, xx, yy, z, r;
struct dot {
    int x, y, p;
    dot(int x, int y, int p) :x(x), y(y), p(p) {}
    dot() { x = 0, y = 0, p = 0; }
    int getccw(dot a, dot b) {    
        double tmp = this->x*a.y + a.x*b.y + b.x*this->- this->y*a.x - a.y*b.x - b.y*this->x;
        if (tmp > 0)return 1;    
        else if (tmp == 0)return 0;    
        else
            return -1;    
    }
    int getdist(dot a) {
        int ret = (this->- a.x)*(this->- a.x) + (this->- a.y)*(this->- a.y);
        return ret;
    }
}d[333];
int bpt[333], visited[333], bb[333];
vector<vector<int>> vt;
int dfs(int here) {
    if (visited[here])return false;
    visited[here] = true;
    for (auto next : vt[here]) {
        if (!bb[next] || dfs(bb[next])) {
            bb[next] = here;
            return true;
        }
    }
    return false;
}
int bipartitematching() {
    int ret = 0;
    for (int i = 1; i <= n; i++) {
        memset(visited, 0sizeof(visited));
        if (dfs(i))ret++;
    }
    return ret;
}
int main() {
    while (scanf("%d"&n) != EOF) {
        if (!n)return 0;
        memset(bb, 0sizeof(bb));
        xx = yy = z = 0;
        vt.clear();
        vt.resize(n + 1);
        for (int i = 1; i <= n; i++) {
            scanf("%d%d%d"&x, &y, &p);
            d[i] = dot(x, y, p);
        }
        scanf("%d%d%d"&a, &b, &r);
        r *= r;
        for (int i = 1; i <= n; i++) {
            bpt[i] = d[a].getccw(d[b], d[i]);
            if (!d[i].p)continue;
            if (bpt[i] > 0)xx++;
            if (bpt[i] < 0)yy++;
        }
        if (xx < yy)z = 1;
        else z = -1;
        for (int i = 1; i <= n; i++) {
            if (bpt[i] != z)continue;
            for (int j = 1; j <= n; j++) {
                if (bpt[i] * bpt[j] != -1)continue;
                if (!d[i].p || !d[j].p)continue;
                if (d[i].getdist(d[j]) <= r&&d[i].p > d[j].p)
                    vt[i].push_back(j);
            }
        }
        printf("Case %d: %d\n"++cnt, bipartitematching());
    }
    return 0;
}
cs


'알고리즘 관련 > UVaOJ' 카테고리의 다른 글

UVaOJ)12797 Letters  (0) 2017.06.27
UVaOJ)11765 Component Placement  (0) 2017.06.27
UVaOJ)12878 Flowery Trails  (0) 2017.06.23
UVaOJ)10968 KuPellaKeS  (0) 2017.06.20
UVaOJ)12645 Water Supply  (0) 2017.06.19