oj.uz

답안 #59193

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
59193 2018-07-21T03:37:18 Z Benq The Forest of Fangorn (CEOI14_fangorn) C++14
50 / 100
 3000 ms 1264 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;
pi p[2000],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) {
    if (eq(x.imag(),0)) return x.real();
    if (eq(x.real(),w)) return w+x.imag();
    if (eq(x.imag(),h)) return w+h+w-x.real();
    return peri-x.imag();
}

int main() {
    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;
    cin >> n;
    F0R(i,n) cin >> p[i].f >> p[i].s;
    F0R(i,n) {
        vector<pair<pi,int>> v;
        F0R(j,n) if (j != i) v.pb({p[i]-p[j],0});
        v.pb({g-p[i],1});
        sort(all(v),[](pair<pi,int> x, pair<pi,int> y) { return atan2(x.f.s,x.f.f) < atan2(y.f.s,y.f.f); });
        int ind = 0; while (!v[ind].s) ind ++;
        a.pb({inter(p[i],v[(ind+sz(v)-1)%sz(v)].f),inter(p[i],v[(ind+1)%sz(v)].f)});
        // for (auto a: v) cout << a.f.f << " " << a.f.s << " " << a.s << "\n";
        // cout << "---\n";
    }
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 3 ms 432 KB Output is correct
4 Correct 2 ms 432 KB Output is correct
5 Correct 3 ms 636 KB Output is correct
6 Correct 2 ms 640 KB Output is correct
7 Correct 6 ms 640 KB Output is correct
8 Correct 5 ms 640 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 640 KB Output is correct
2 Correct 4 ms 640 KB Output is correct
3 Correct 6 ms 640 KB Output is correct
4 Correct 9 ms 640 KB Output is correct
5 Correct 9 ms 640 KB Output is correct
6 Correct 26 ms 640 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 4 ms 640 KB Output is correct
9 Correct 9 ms 640 KB Output is correct
10 Correct 39 ms 708 KB Output is correct
11 Correct 38 ms 732 KB Output is correct
12 Correct 69 ms 732 KB Output is correct

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 732 KB Output is correct
2 Correct 4 ms 760 KB Output is correct
3 Correct 5 ms 772 KB Output is correct
4 Correct 1218 ms 1264 KB Output is correct
5 Correct 236 ms 1264 KB Output is correct
6 Execution timed out 3055 ms 1264 KB Time limit exceeded

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3052 ms 1264 KB Time limit exceeded
2 Halted 0 ms 0 KB -