oj.uz

Submission #59311

# Submission time Handle Problem Language Result Execution time Memory
59311 2018-07-21T13:24:42 Z Benq The Forest of Fangorn (CEOI14_fangorn) C++14
100 / 100
 345 ms 2104 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
 
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
 
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
 
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
 
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
 
const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;
 
ld w,h,peri;
int c,n;
vpi C,p;
pi g;
vector<pair<cd,cd>> a;
 
pi operator-(const pi& l, const pi& r) {
    return {l.f-r.f,l.s-r.s};
}
 
cd inter(pi x, pi y) {
    ld mul = 1e18;
    if (y.f > 0) mul = min(mul,(ld)(w-x.f)/y.f);
    if (y.f < 0) mul = min(mul,-(ld)x.f/y.f);
    if (y.s > 0) mul = min(mul,(ld)(h-x.s)/y.s);
    if (y.s < 0) mul = min(mul,-(ld)x.s/y.s);
    // cout << "AH " << mul << "\n";
    return {x.f+mul*y.f,x.s+mul*y.s};
}
 
bool eq(ld a, ld b) {
    return abs(a-b) <= 1e-9;
}
 
ld GET(cd x) {
    ld dis = min(abs(x.real()),abs(w-x.real()));
    dis = min(dis,min(abs(x.imag()),abs(h-x.imag())));
    if (dis == abs(x.imag())) return x.real();
    if (dis == abs(w-x.real())) return w+x.imag();
    if (dis == abs(h-x.imag())) return w+h+w-x.real();
    return peri-x.imag();
}

int r() {
    return rand() % 1000000000;
}

void input() {
     
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> w >> h >> g.f >> g.s;
    peri = 2*(w+h);
    cin >> c; C.resize(c); // assume connected region
    F0R(i,c) {
        cin >> C[i].f >> C[i].s;
        // C[i].f = r(), C[i].s = r();
    }
    cin >> n; p.resize(n);
    F0R(i,n) {
        cin >> p[i].f >> p[i].s;
        // p[i].f = r(), p[i].s = r();
    }
}

ld nor(ld x) {
    if (x <= 0) x += 2*M_PIl;
    return x;
}

int main() {
    input();
    F0R(i,n) {
        pi G = g-p[i];
        pair<ld,pi> bes1, bes2;
        bes1 = bes2 = {2*M_PIl,G};
        
        ld X = atan2(G.s,G.f);
        vector<pair<pi,int>> v;
        F0R(j,n) if (j != i) {
            pi P = p[i]-p[j];
            ld x = atan2(P.s,P.f);
            if (nor(X-x) < bes1.f) bes1 = {nor(X-x),P};
            if (nor(x-X) < bes2.f) bes2 = {nor(x-X),P};
        }
        a.pb({inter(p[i],bes1.s),inter(p[i],bes2.s)});
    }
    
    vector<pair<ld,int>> z;
    for (auto x: a) {
        ld l = GET(x.f), r = GET(x.s);
        if (l > r) r += peri;
        z.pb({l-peri,1}); z.pb({r-peri,-1});
        z.pb({l,1}); z.pb({r,-1});
    }
    F0R(i,c) z.pb({GET(cd(C[i].f,C[i].s)),i+1+MOD});
    sort(all(z));
    int co = 0;
    vi res;
    for (auto x: z) {
        if (x.s == -1) co --;
        else if (x.s == 1) co ++;
        else {
            x.s -= MOD;
            if (co == sz(a)) res.pb(x.s);
        }
    }
    cout << sz(res) << "\n";
    sort(all(res));
    for (int i: res) cout << i << " ";
}
 
/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 380 KB Output is correct
2 Correct 3 ms 456 KB Output is correct
3 Correct 3 ms 456 KB Output is correct
4 Correct 3 ms 472 KB Output is correct
5 Correct 2 ms 472 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 3 ms 600 KB Output is correct
8 Correct 2 ms 600 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 692 KB Output is correct
2 Correct 3 ms 692 KB Output is correct
3 Correct 3 ms 692 KB Output is correct
4 Correct 76 ms 864 KB Output is correct
5 Correct 19 ms 864 KB Output is correct
6 Correct 341 ms 1252 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 1488 KB Output is correct
2 Correct 276 ms 1976 KB Output is correct
3 Correct 345 ms 2008 KB Output is correct
4 Correct 221 ms 2104 KB Output is correct