USACO January 2014 Contest

링크

Cow Curling

FJ의 농장에서 컬링 대회가 열렸다. 이 컬링 대회의 규칙은 일반 대회와는 조금 다르다.

겨루는 두 팀에게는 각각 $N$개의 돌이 주어진다.

만약, 한 팀의 세 개의 돌이 이루는 삼각형 내부에 상대 팀의 돌이 들어있다면, 이 돌은 포획되었다고 한다. (선분 위에 올라간 경우도 포함한다.)

각 팀의 점수는 상대 팀의 포획된 돌의 수로 계산된다.

두 팀의 돌의 배치가 2차원 평면 상의 좌표로 주어질 때, 각 팀의 점수를 계산하여라.

 

풀이

아이디어는 굉장히 쉽다. 그냥 각 팀의 convex hull을 각각 만들고, 상대 팀의 돌이 몇 개 들어가는지를 계산하면 된다.

이때, 볼록다각형의 내/외부점 판별 알고리즘을 이용하면 된다.

이 문제의 경우, 각 점에 대해서 따로따로 판별할 필요없이 한 번에 스위핑 하듯이, 두 포인터 하듯이 하면 로그를 뗄 수 있다.

아무튼, 기하이기 때문에 예외 처리와 빡센 구현이 핵심이다... 그나마 점의 개수가 3 이상이고, 점들이 distinct 하다는 조건이 있어서 코드를 짜다 미쳐버리진 않았다.

 

코드 속에 있는 정렬 조건들은 이 블로그의 실수 없는 계산기하(1)에서 소개하고 있으니 궁금하면 참고하기 바란다...

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define per(i,a,b) for (auto i = (b); i >= (a); --i)
#define all(x) begin(x), end(x)
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)
#define fi first
#define se second
#define dbg(...) fprintf(stderr,__VA_ARGS__)

#pragma region Geometry
using P = complex<ll>; using ld = long double; using Poly = vector<P>;
const ld PI = acos(-1.0L), TAU = 2*PI;
#define X real()
#define Y imag()
#define dot(u,v) (conj(u)*(v)).X
#define cross(u,v) (conj(u)*(v)).Y
#define norm(u) dot(u,u)
int ccw(P a, P b, P c) {
    auto v = cross(b-a,c-b);
    if (v < 0) return -1;
    else if (v > 0) return 1;
    return 0;
}
ld abs(P u) {return sqrt(ld(norm(u)));}
istream &operator >> (istream &is, P &p) {ll x, y; is >> x >> y; p = {x,y}; return is;}
namespace std { bool operator < (P u, P v) {return u.X == v.X ? u.Y < v.Y : u.X < v.X;} }
#pragma endregion

Poly convex_hull(vector<P> &p) {
    sort(p.begin(),p.end());
    Poly up(siz(p)), lo(siz(p));
    int u = 0, l = 0, i = 0, j = siz(p)-1;
    rep(_,1,siz(p)) {
        while (u >= 2 and ccw(up[u-2],up[u-1],p[i]) >= 0) --u;
        while (l >= 2 and ccw(lo[l-2],lo[l-1],p[j]) >= 0) --l;
        up[u++] = p[i++], lo[l++] = p[j--];
    }
    up.resize(u-1), lo.resize(l-1);
    up.insert(up.end(),lo.begin(),lo.end());
    return up;
}

int solve(Poly a, vector<P> b) {
    // 볼록 다각형 a에 속한 b 속 점의 개수를 반환
    // 볼록 다각형 속 점들은 반시계 방향으로 정렬되어 있다.
    P o = a[0], x = a[1];
    auto half = [o,x](P p) {
        if (cross(x-o,p-o) < 0) return true;
        return cross(x-o,p-o) == 0 and dot(x-o,p-o) < 0;
    };
    auto polar_compare = [o,&half](P u, P v) {
        if (half(u) != half(v)) return half(u) < half(v);
        return cross(u-o,v-o) > 0;
    };
    sort(all(b),polar_compare);
    int i = 1, cnt = 0;
    for (auto p : b) {
        if (i < siz(a) and !(ccw(a[0],a[i],p) == 0 or polar_compare(a[i],p))) continue;
        while (i+1 < siz(a) and !polar_compare(p,a[i+1])) i++;
        if (i+1 < siz(a)) {
            if (ccw(a[i],p,a[i+1]) <= 0) cnt++;
        } else {
            if (ccw(a[0],a[i],p) == 0) {
                if (norm(p-o) < norm(a[i]-o) and dot(p-o,a[i]-o) > 0)
                    cnt++;
            }
        }
    }
    return cnt;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n; cin >> n;
    vector<P> a(n), b(n); // n >= 3
    for (auto &p : a) cin >> p;
    for (auto &p : b) cin >> p;
    Poly x = convex_hull(a), y = convex_hull(b);
    reverse(all(x)), reverse(all(y));
    cout << solve(x,b) << ' ' << solve(y,a);
}

 

Building a Ski Course

한겨울에 사용하지 않는 FJ의 농장 한귀퉁이에서 $N\times M$ 크기의 영역을 스키 대회의 스키장으로 활용하려고 한다.

각 단위 영역은 거칠거나 부드러운 눈으로 쌓여있다. 스키 선수들은 다양한 질감의 눈이 섞여있을 때 더 재미있게 대회를 즐길 수 있다.

그래서 스키 선수들의 의견을 종합해 $N\times M$ 크기의 스키장 관리 계획이 세워졌다.

각 단위 영역에는 문자 'R' 또는 'S'가 있는데, 이는 거친(rough)의 질감의 눈과 부드러운(smooth) 질감의 눈을 뜻한다.

FJ는 $B\times B$ 영역을 선택해서 전부 'R'로 찍어내거나 'S'로 찍어낼 수 있다. FJ는 이 작업을 여러번 반복해 관리 계획대로 스키장을 가공할 것이다. 처음에 스키장은 'R'과 'S', 그 어떤 상태도 아니다.

만약 $B$가 매우 크다면 관리 계획대로 스키장을 가공하는 것이 불가능할 수 있다. 따라서 관리 계획대로 스키장을 가공하는 것이 가능한 $B$의 최댓값을 구하여라.

 

풀이

마지막에 찍어낸 $B\times B$ 영역은 항상 내부의 모든 위치가 같은 상태로 나타날 것이다.

그렇게 거꾸로 $B\times B$ 영역들을 벗겨내서 아무것도 없는 상태를 만들 수 있다면 이 $B$는 관리 계획대로 스키장을 가공하는 것이 가능하다.

$B'<B$에 대해, $B$에서 가공 가능하다면 $B'$도 가공 가능하므로 파라매트릭 서치를 활용하면 좋겠다는 생각을 할 수 있다.

 

이를 종합하면 문제를 풀 수 있다.

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define per(i,a,b) for (auto i = (b); i >= (a); --i)
#define all(x) begin(x), end(x)
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)
#define fi first
#define se second
#define dbg(...) fprintf(stderr,__VA_ARGS__)

const int R = 103, C = R;
int r, c;
char s[R][C], t[R][C];

bool valid(int x) {
    rep(i,1,r) rep(j,1,c) t[i][j] = s[i][j];
    rep(_,1,r*c) {
        bool did = false;
        rep(i,1,r-x+1) rep(j,1,c-x+1) {
            bool rr = false, ss = false;
            rep(k,i,i+x-1) rep(l,j,j+x-1) {
                rr |= (t[k][l] == 'R');
                ss |= (t[k][l] == 'S');
            }
            if (rr xor ss) {
                did = true;
                rep(k,i,i+x-1) rep(l,j,j+x-1) t[k][l] = '?';
            }
        }
        if (not did) {
            rep(i,1,r) rep(j,1,c) if (t[i][j] != '?') return false;
            return true;
        }
    }
    assert(0);
}

int main() {
    scanf("%d %d ", &r, &c);
    rep(i,1,r) scanf(" %s ", s[i]+1);
    int a = 1, b = min(r,c), m;
    while (a <= b) {
        m = (a+b)/2;
        if (valid(m)) a = m+1;
        else b = m-1;
    }
    printf("%d", b);
}

 

Ski Course Rating

스키장의 $N\times M$ 영역의 각 단위 영역마다 높이 $h_{i,j}$가 존재한다.

어떤 사람의 실력이 $D$라면 한 단위 영역과 인접한 다른 단위 영역 사이의 높이 차이가 $D$ 이하일 경우 그곳으로 이동할 수 있다.

스키장의 일부 단위 영역이 시작 지점으로 선정되었다.

각 시작 지점은 난이도 $P$를 갖는데, 이는 실력이 $P$ 이상인 사람들만이 시작 지점에서부터 $T$개 이상의 지점까지 이동할 수 있음을 의미한다.

모든 시작 지점들의 난이도의 합을 구하여라.

 

풀이

병렬 이진 탐색을 이용하여 풀 수 있다. 자세한 풀이는 준비중이다.