oj.uz

Submission #101043

# Submission time Handle Problem Language Result Execution time Memory
101043 2019-03-16T06:50:16 Z Bruteforceman The Forest of Fangorn (CEOI14_fangorn) C++11
0 / 100
 780 ms 744 KB 
#include "bits/stdc++.h"
using namespace std;
 
struct point {
    long long x, y;
    int id;
    point () {}
    point (long long x, long long y) : x(x), y(y) {}
    point operator + (point p) {
        return point(x + p.x, y + p.y);
    }
    point operator - (point p) {
        return point(x - p.x, y - p.y);
    }
} c[10010], t[2005];
point corn[4];

int cnt[10010];
 
long long cross(point a, point b) {
    return a.x * b.y - a.y * b.x;
}
int side(point a) {
    if(a.y > 0 || (a.y == 0 && a.x >= 0)) return 0;
    else return 1;
}
bool cmp(point a, point b) {
    if(side(a) == side(b)) {
        return cross(a, b) > 0;
    } else {
        return side(a) < side(b);
    }
}
 
int main(int argc, char const *argv[])
{
    int w, h;
    point s;
    scanf("%d %d", &w, &h);
    scanf("%lld %lld", &s.x, &s.y);
 
    corn[0] = point(0, 0);
    corn[1] = point(w, 0);
    corn[2] = point(w, h);
    corn[3] = point(0, h);

    int C;
    scanf("%d", &C);
    for(int i = 1; i <= C; i++) {
        scanf("%lld %lld", &c[i].x, &c[i].y);
        for(int j = 0; j < 4; j++) {
            assert(c[i].x != corn[j].x || c[i].y != corn[j].y);
        }
    }
    int N;
    scanf("%d", &N);
    for(int i = 1; i <= N; i++) {
        scanf("%lld %lld", &t[i].x, &t[i].y);
    }
    for(int i = 1; i <= N; i++) {
        vector <point> v;
        for(int j = 1; j <= N; j++) {
            if(j == i) continue;
            point p = t[i] - t[j];
            p.id = 0;
            v.emplace_back(p);
        }
        point p = s - t[i];
        p.id = -1;
        v.emplace_back(p);
        sort(v.begin(), v.end(), cmp);
        for(int j = 1; j <= C; j++) {
            point p = c[j] - t[i];
            p.id = j;
            v.emplace_back(p);
        }
        int pos = 0;
        for(int j = 0; j < v.size(); j++) {
            if(v[j].id < 0) {
                pos = j;
                break;
            }
        }
        int cur = pos;
        int sz = v.size();
        while(v[cur].id != 0) {
            if(v[cur].id > 0) {
                cnt[v[cur].id] += 1;
            }
            cur = (cur + 1) % sz;
        }
        cur = pos;
        while(v[cur].id != 0) {
            if(v[cur].id > 0) {
                cnt[v[cur].id] += 1;
            }
            cur = (sz + cur - 1) % sz;
        }
    }
    int ans = 0;
    for(int i = 1; i <= C; i++) {
        if(cnt[i] == N) {
            ++ans;
        }
    }
    printf("%d\n", ans);
    for(int i = 1; i <= C; i++) {
        if(cnt[i] == N) {
            printf("%d ", i);
        }
    }
    if(ans) printf("\n");
    return 0;
}

Compilation message

fangorn.cpp: In function 'int main(int, const char**)':
fangorn.cpp:78:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < v.size(); j++) {
                        ~~^~~~~~~~~~
fangorn.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &w, &h);
     ~~~~~^~~~~~~~~~~~~~~~~
fangorn.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld", &s.x, &s.y);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fangorn.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &C);
     ~~~~~^~~~~~~~~~
fangorn.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld", &c[i].x, &c[i].y);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fangorn.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
fangorn.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld", &t[i].x, &t[i].y);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Incorrect 2 ms 384 KB Output isn't correct
3 Incorrect 2 ms 384 KB Output isn't correct
4 Incorrect 3 ms 384 KB Output isn't correct
5 Runtime error 2 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Correct 2 ms 384 KB Output is correct
8 Incorrect 3 ms 384 KB Output isn't correct

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Incorrect 4 ms 384 KB Output isn't correct
3 Incorrect 3 ms 384 KB Output isn't correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Incorrect 2 ms 384 KB Output isn't correct
8 Incorrect 2 ms 256 KB Output isn't correct
9 Incorrect 2 ms 384 KB Output isn't correct
10 Incorrect 6 ms 384 KB Output isn't correct
11 Incorrect 7 ms 384 KB Output isn't correct
12 Correct 8 ms 384 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 780 ms 744 KB Output isn't correct
2 Halted 0 ms 0 KB -