답안 #130438

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
130438 2019-07-15T08:03:42 Z 송준혁(#3152) Fence (CEOI08_fence) C++14
50 / 100
3 ms 420 KB
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;

int N, M, ans=1234567890, C, W;
pii P[110], T[110], CH[110];
bool chk[110];

LL CCW(pii a, pii b, pii c){
    pii p = pii(b.first-a.first, b.second-a.second);
    pii q = pii(c.first-a.first, c.second-a.second);
    return p.first*q.second - q.first*p.second;
}

int main(){
    scanf("%d %d", &N, &M);
    for (int i=0; i<N; i++) {
        scanf("%d %d", &P[i].first, &P[i].second);
        if (P[0].first > P[i].first) swap(P[0], P[i]);
    }
    for (int i=0; i<M; i++) scanf("%d %d", &T[i].first, &T[i].second);
    sort(P+1, P+N, [&](pii a, pii b){return CCW(P[0], a, b) > 0;});
    CH[0] = P[0], CH[1] = P[1], C=2;
    for (int i=2; i<N; i++){
        while (C > 1 && CCW(CH[C-2], CH[C-1], P[i]) < 0) C--;
        CH[C++] = P[i];
    }
    for (int i=0; i<M; i++){
        chk[i] = true;
        for (int j=0; j<C; j++) {
            if (CCW(CH[j], CH[(j+1)%C], T[i]) < 0){
                chk[i] = false, W++;
                break;
            }
        }
    }
    if (W == M){
        printf("%d\n", 111*M);
        return 0;
    }
    for (int i=0; i<C; i++){
        int cnt=1, t=i, k=i+1;
        while (1){
            for (int j=0; j<M; j++){
                if (chk[j] && CCW(CH[t], CH[k], T[j]) < 0){
                    t = (k+C-1)%C, cnt++;
                    for (int p=0; p<N; p++){
                        bool tf = true;
                        for (int q=0; q<M; q++){
                            if (chk[j] && (CCW(CH[t], P[p], T[q]) < 0 || CCW(P[p], CH[i], T[q]) < 0)){
                                tf = false;
                                break;
                            }
                        }
                        if (tf) ans = min(ans, cnt+1);
                    }
                    break;
                }
            }
            if (k == i) break;
            k = (k+1)%C;
        }
        ans = min(ans, cnt);
    }
    printf("%d\n", ans*20 + W*111);
    return 0;
}

Compilation message

fence.cpp: In function 'int main()':
fence.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &N, &M);
     ~~~~~^~~~~~~~~~~~~~~~~
fence.cpp:19:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &P[i].first, &P[i].second);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fence.cpp:22:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i=0; i<M; i++) scanf("%d %d", &T[i].first, &T[i].second);
                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 380 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 384 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 420 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -