oj.uz

Submission #101054

# Submission time Handle Problem Language Result Execution time Memory
101054 2019-03-16T07:50:04 Z Bruteforceman The Forest of Fangorn (CEOI14_fangorn) C++11
100 / 100
 1697 ms 2460 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;
    }
    inline int side(point &a) {
        if(a.y > 0 || (a.y == 0 && a.x >= 0)) return 0;
        else return 1;
    }
    inline 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);
        }
     
        vector <point> prec;
        for(int i = 1; i <= C; i++) {
            point p = c[i] - point(1, 1);
            p.id = i;
            prec.emplace_back(p);
        }
        sort(prec.begin(), prec.end(), cmp);
        for(auto &i : prec) {
            i.x += 1;
            i.y += 1;
        } 
        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> r;
            for(int j = 1; j <= N; j++) {
                if(j == i) continue;
                point p = t[i] - t[j];
                p.id = 0;
                r.emplace_back(p);
            }
            point p = s - t[i];
            p.id = -1;
            r.emplace_back(p);
            sort(r.begin(), r.end(), cmp);
            int pt = 0;
            while(pt < C && prec[pt].x == w && 0 < prec[pt].y && prec[pt].y < t[i].y) {
                ++pt;
            }
            vector <point> u;
            for(int j = 0; j < C; j++) {
                int id = prec[(j + pt) % C].id;
                point p = c[id] - t[i];
                p.id = id;
                u.emplace_back(p);
            }   
            vector <point> v;
            merge(r.begin(), r.end(), u.begin(), u.end(), back_inserter(v), cmp);
     
            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;
                if(cur == sz) cur = 0;
            }
            cur = pos;
            while(v[cur].id != 0) {
                if(v[cur].id > 0) {
                    cnt[v[cur].id] += 1;
                }
                --cur;
                if(cur < 0) cur = sz - 1;
            }
        }
        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:96:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0; j < v.size(); j++) {
                            ~~^~~~~~~~~~
fangorn.cpp:39:14: 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:14: 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:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &C);
         ~~~~~^~~~~~~~~~
fangorn.cpp:50:18: 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:65:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &N);
         ~~~~~^~~~~~~~~~
fangorn.cpp:67:18: 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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 121 ms 472 KB Output is correct
5 Correct 28 ms 432 KB Output is correct
6 Correct 589 ms 796 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 728 ms 772 KB Output is correct
2 Correct 1697 ms 2244 KB Output is correct
3 Correct 1597 ms 2180 KB Output is correct
4 Correct 1584 ms 2460 KB Output is correct