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보다 많은 두 점을 서로 매칭시켜준 뒤 최대매칭을 구해주면 된다.

 

#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->y - 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->x - a.x)*(this->x - a.x) + (this->y - a.y)*(this->y - 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, 0, sizeof(visited));
        if (dfs(i))ret++;
    }
    return ret;
}
int main() {
    while (scanf("%d", &n) != EOF) {
        if (!n)return 0;
        memset(bb, 0, sizeof(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;
}