oj.uz

Submission #33989

# Submission time Handle Problem Language Result Execution time Memory
33989 2017-11-06T01:01:57 Z imaxblue The Forest of Fangorn (CEOI14_fangorn) C++14
100 / 100
 2626 ms 2600 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define pii pair<int, int>
#define p3i pair<pii, int>
#define pll pair<ll, ll>
#define p3l pair<pll, ll>
#define lseg L, (L+R)/2, N*2+1
#define rseg (L+R)/2+1, R, N*2+2
#define ub upper_bound
#define lb lower_bound
#define pq priority_queue
#define MN 1000000007LL
#define fox(k, x) for (int k=0; k<x; ++k)
#define fox1(k, x) for (int k=1; k<=x; ++k)
#define foxr(k, x) for (int k=x-1; k>=0; --k)
#define fox1r(k, x) for (int k=x; k>0; --k)
#define ms multiset
#define flood(x) memset(x, 0x3f3f3f3f, sizeof x)
#define drain(x) memset(x, 0, sizeof x)
#define rng() (rand() >> 3)*rand()
#define GT(X, Y) (X>Y+0.0000001)
#define LT(X, Y) (X+0.0000001<Y)
#define EQ(X, Y) (!GT(X, Y) && !LT(X, Y))

int n, c, a, b, w, h, dir, p, q,
    x[2005], y[2005], cx[10005], cy[10005];
double sl, t;
bool u[10005], ans[10005];
double comp(double X, double Y){
    if (EQ(Y, 0)) return X;
    if (EQ(X, w)) return Y+MN;
    if (EQ(Y, h)) return w-X+2*MN;
    return h-Y+3*MN;
}
double get_point(int B, int A){
    if (x[B]==x[A]){
        if (y[B]<y[A]){
            return comp(x[A], 0);
        }
        if (y[B]>y[A]){
            return comp(x[A], h);
        }
    }
    if (y[B]==y[A]){
        if (x[B]<x[A]){
            return comp(0, y[A]);
        }
        if (x[B]>x[A]){
            return comp(w, y[A]);
        }
    }
    sl=double(y[B]-y[A])/(x[B]-x[A]);
    if (x[B]-x[A]<0){
        t=y[A]+(-x[A])*sl;
        if ((GT(t, 0) || EQ(t, 0)) && (LT(t, h) || EQ(t, h)))
            return comp(0, t);
    }
    if (x[B]-x[A]>0){
        t=y[A]+(w-x[A])*sl;
        if ((GT(t, 0) || EQ(t, 0)) && (LT(t, h) || EQ(t, h)))
            return comp(w, t);
    }
    if (y[B]-y[A]<0){
        t=x[A]+(-y[A])/sl;
        if ((GT(t, 0) || EQ(t, 0)) && (LT(t, w) || EQ(t, w)))
            return comp(t, 0);
    }
    if (y[B]-y[A]>0){
        t=x[A]+(h-y[A])/sl;
        if ((GT(t, 0) || EQ(t, 0)) && (LT(t, w) || EQ(t, w)))
            return comp(t, h);
    }
    //cout << A << ' ' << B << ' ' << sl << endl;
    //exit(1);
}
vector<pair<double, int> > v;
int main(){
    //cout << EQ(0, 0);
    //cout << (!GT(4.0, 4.0) && !LT(4.0, 4.0));
    cin >> w >> h >> x[0] >> y[0] >> q;
    fox1(l, q) cin >> cx[l] >> cy[l];
    cin >> n;
    fox1(l, n){
        cin >> x[l] >> y[l];
    }
    memset(ans, 1, sizeof ans);
    fox1(l, n){
        v.clear(); drain(u);
        fox1(l2, n){
            if (l2==l) continue;
            v.pb(mp(get_point(l, l2), 0));
        }
        fox1(l2, q){
            v.pb(mp(comp(cx[l2], cy[l2]), l2));
        }
        v.pb(mp(get_point(0, l), -1));
        sort(v.begin(), v.end());
        fox(l, v.size()){
            //printf("%.0f ", v[l].x);
            //cout << ":" << v[l].y << ' ' << endl;
            if (v[l].y==-1){
                for (p=l; v[p].y!=0; p=(p+v.size()-1)%v.size());
                //cout << p << ' ' << v[p].y<< endl;
                for (p=(p+1)%v.size(); v[p].y!=0; p=(p+1)%v.size()){
                    //cout << "^";
                    if (v[p].y!=-1) u[v[p].y]=1;
                }
            }
        }
        fox1(l, q){
            //if (u[l]) cout << "*";
            ans[l]&=u[l];
        }
        //cout << endl;
    }
    c=0;
    fox1(l, q)
        if (ans[l]) c++;
    cout << c << endl;
    fox1(l, q)
        if (ans[l]) cout << l << ' ';
    cout << endl;
    return 0;
}

Compilation message

fangorn.cpp: In function 'int main()':
fangorn.cpp:18:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fox(k, x) for (int k=0; k<x; ++k)
                                  ^
fangorn.cpp:103:9: note: in expansion of macro 'fox'
         fox(l, v.size()){
         ^
fangorn.cpp: In function 'double get_point(int, int)':
fangorn.cpp:80:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
30.0 / 30.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2132 KB Output is correct
2 Correct 0 ms 2132 KB Output is correct
3 Correct 0 ms 2132 KB Output is correct
4 Correct 89 ms 2132 KB Output is correct
5 Correct 16 ms 2132 KB Output is correct
6 Correct 363 ms 2272 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 636 ms 2272 KB Output is correct
2 Correct 2563 ms 2600 KB Output is correct
3 Correct 2626 ms 2600 KB Output is correct
4 Correct 1386 ms 2600 KB Output is correct