Submission #59195

#	Time	Username	Problem	Language	Result	Execution time	Memory
59195		Benq	The Forest of Fangorn (CEOI14_fangorn)	C++14	50 / 100	3031 ms	976 KiB

fangorn

#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<double> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<double,double> pd;

typedef vector<int> vi;
typedef vector<double> 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;

double 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) {
    double mul = 1e18;
    if (y.f > 0) mul = min(mul,(double)(w-x.f)/y.f);
    if (y.f < 0) mul = min(mul,-(double)x.f/y.f);
    if (y.s > 0) mul = min(mul,(double)(h-x.s)/y.s);
    if (y.s < 0) mul = min(mul,-(double)x.s/y.s);
    // cout << "AH " << mul << "\n";
    return {x.f+mul*y.f,x.s+mul*y.s};
}

bool eq(double a, double b) {
    return abs(a-b) <= 1e-8;
}

double 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<double,int>> z;
    for (auto x: a) {
        double 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 / 30
• Subtask 2: 20 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 20