oj.uz

Submission #130373

# Submission time Handle Problem Language Result Execution time Memory
130373 2019-07-15T05:03:37 Z 송준혁(#3152) Fence (CEOI08_fence) C++14
60 / 100
 2 ms 376 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-1, cnt++;
                    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);
                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Incorrect 2 ms 256 KB Output isn't correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 256 KB Output isn't correct