oj.uz

Submission #116942

# Submission time Handle Problem Language Result Execution time Memory
116942 2019-06-14T07:46:59 Z JohnTitor The Forest of Fangorn (CEOI14_fangorn) C++11
100 / 100
 112 ms 640 KB 
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k) for(int i=(j); i<=(k); i++)
#define FFOR(i, j, k) for(int i=(j); i<(k); i++)
#define DFOR(i, j, k) for(int i=(j); i>=(k); i--)
#define bug(x) cerr<<#x<<" = "<<(x)<<'\n'
#define pb push_back
#define mp make_pair
#define bit(s, i) (((s)>>(i))&1LL)
#define mask(i) ((1LL<<(i)))
#define builtin_popcount __builtin_popcountll
#define __builtin_popcount __builtin_popcountll
using ll=long long; using ld=long double;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); const ld pi=acos(0)*2;
template <typename T> inline void read(T &x){char c; bool nega=0; while((!isdigit(c=getchar()))&&(c!='-')); if(c=='-'){nega=1; c=getchar();} x=c-48; while(isdigit(c=getchar())) x=x*10+c-48; if(nega) x=-x;}
template <typename T> inline void writep(T x){if(x>9) writep(x/10); putchar(x%10+48);}
template <typename T> inline void write(T x){if(x<0){ putchar('-'); x=-x;} writep(x);}
template <typename T> inline void writeln(T x){write(x); putchar('\n');}
#define taskname "Fangorn"
int n, c;
class point{
public:
    ll x, y;
    void input(){
        read(x);
        read(y);
    }
    point operator -(){
        point res;
        res.x=-x;
        res.y=-y;
        return res;
    }
    bool ccw(point A, point B){
        A.x-=x;
        A.y-=y;
        B.x-=x;
        B.y-=y;
        return (A.x*B.y-B.x*A.y)>0;
    }
    bool cw(point A, point B){
        A.x-=x;
        A.y-=y;
        B.x-=x;
        B.y-=y;
        return (A.x*B.y-B.x*A.y)<0;
    }
    bool ccw(point A, point B, point C){
        if(ccw(A, C)==ccw(B, C)) return ccw(A, B);
        else return ccw(B, C);
    }
    bool cw(point A, point B, point C){
        if(cw(A, C)==cw(B, C)) return cw(A, B);
        else return cw(B, C);
    }
} s, p[10001], t[2001];
bool good[10001];
ll w, h;
int main(){
    #ifdef Aria
        if(fopen(taskname".in", "r"))
            freopen(taskname".in", "r", stdin);
    #endif // Aria
    read(w);
    read(h);
    s.input();
    read(c);
    FOR(i, 1, c) p[i].input();
    read(n);
    FOR(i, 1, n) t[i].input();
    FOR(i, 1, c) good[i]=1;
    FOR(i, 1, n){
        point bccw, bcw;
        bool first=1;
        FOR(j, 1, n) if(j!=i){
            point R=p[j];
            R.x=t[i].x*2-t[j].x;
            R.y=t[i].y*2-t[j].y;
            if(first){
                first=0;
                bccw=bcw=R;
            }
            else{
                if(t[i].ccw(bccw, R, s)) bccw=R;
                if(t[i].cw(bcw, R, s)) bcw=R;
            }
        }
        FOR(j, 1, c) if(good[j]) good[j]=t[i].ccw(bccw, p[j], bcw);
//        bug(i);
//        cerr<<bccw.x<<' '<<bccw.y<<' '<<bcw.x<<' '<<bcw.y<<'\n';
    }
    int ans=0;
    FOR(i, 1, c) ans+=good[i];
    writeln(ans);
    FOR(i, 1, c) if(good[i]) write(i), putchar(' ');
    putchar('\n');
}

Compilation message

fangorn.cpp: In function 'int main()':
fangorn.cpp:36:12: warning: '*((void*)& bccw +8)' may be used uninitialized in this function [-Wmaybe-uninitialized]
         A.y-=y;
         ~~~^~~
fangorn.cpp:73:15: note: '*((void*)& bccw +8)' was declared here
         point bccw, bcw;
               ^~~~
fangorn.cpp:35:12: warning: 'bccw' may be used uninitialized in this function [-Wmaybe-uninitialized]
         A.x-=x;
         ~~~^~~
fangorn.cpp:73:15: note: 'bccw' was declared here
         point bccw, bcw;
               ^~~~

Subtask #1
30.0 / 30.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
30.0 / 30.0

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

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 416 KB Output is correct
2 Correct 112 ms 512 KB Output is correct
3 Correct 57 ms 640 KB Output is correct
4 Correct 73 ms 640 KB Output is correct