Submission #61850

#	Time	Username	Problem	Language	Result	Execution time	Memory
61850		Benq	Printed Circuit Board (CEOI12_circuit)	C++11	25 / 100	1077 ms	24748 KiB

circuit

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

// library

pi operator+(const pi& l, const pi& r) { return {l.f+r.f,l.s+r.s}; }
pi operator+=(pi& l, const pi& r) { return l = l+r; }

void prin(pair<pi,pi> x) {
    cout << x.f.f << " " << x.f.s << " " << x.s.f << " " << x.s.s << "\n----\n";
}

ld cross(cd a, cd b) { return (conj(a)*b).imag(); }
ld area(cd a, cd b, cd c) { return cross(b-a,c-a); }
ld dot(cd a, cd b) { return (conj(a)*b).real(); }

cd reflect(cd p, cd a, cd b) { return a+conj((p-a)/(b-a))*(b-a); }
cd proj(cd p, cd a, cd b) { return (p+reflect(p,a,b))/(ld)2; }

cd line(cd a, cd b, cd c, cd d) {
    ld x = area(a,b,c), y = area(a,b,d);
    return (x*d-y*c)/(x-y);
}

ld eval(pair<pi,pi> x, pi y) {
    return norm(line(cd(x.f.f,x.f.s),cd(x.s.f,x.s.s),cd(y.f,y.s),cd(0,0)));
}

int N, rv[MX];
vi ev[MX][2], v, ans;
pi p[MX]; 

// 1, b: ins
// b, a, -1: del 
// a, 0, 0: query

bool equiv(pi a, pi b) { return (ll)a.f*b.s == (ll)a.s*b.f; }

bool cmp(pi a, pi b) {
    if (equiv(a,b)) return a < b;
    return (ll)a.s*b.f < (ll)b.s*a.f;
}

void init() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N;
    FOR(i,1,N+1) cin >> p[i].f >> p[i].s;
    FOR(i,1,N+1) v.pb(i);
    sort(all(v),[](int a, int b) { return cmp(p[a],p[b]); });
    F0R(i,N) rv[v[i]] = i;
    
    FOR(i,1,N+1) {
        int a = i, b = i%N+1;
        if (rv[a] > rv[b]) swap(a,b);
        if (!equiv(p[a],p[b])) {
            ev[b][0].pb(a);
            ev[a][1].pb(b);
        }
    }
}

pi cur;

struct CMP {
    bool operator()(const pair<pi,pi>& l, const pair<pi,pi>& r) {
        if (cur == mp(-1,-1)) {
            /*cout << "OOPS\n";
            prin(l);
            prin(r);
            exit(0);*/
            if (l.s == cur) return norm(cd(l.f.f,l.f.s)) < eval(r,l.f);
            if (r.s == cur) return eval(l,r.f) < norm(cd(r.f.f,r.f.s));
            exit(5);
        } else {
            return eval(l,cur) < eval(r,cur);
        }
    }
};

set<pair<pi,pi>,CMP> S;

void del(int l, int r) {
    if (l == 0) return;
    FOR(i,l,r+1)  for (int j: ev[v[i]][0]) S.erase({p[j],p[v[i]]});
}

void tri(int l, int r) {
    cur = {-1,-1};
    if (S.lb({p[v[l]],cur}) == S.begin()) ans.pb(v[l]);
}

void ins(int l, int r) {
    if (r == sz(v)-1) return;
    cur = p[v[r]]+p[v[r+1]];
    FOR(i,l,r+1) for (int j: ev[v[i]][1]) S.insert({p[v[i]],p[j]});
}

void answer(int l, int r) {
    del(l,r);
    tri(l,r);
    ins(l,r);
}

int main() {
    init();
    for (int i = 0; i < sz(v); ) {
        int I = i;
        while (i < sz(v) && equiv(p[v[I]],p[v[i]])) i ++;
        answer(I,i-1);
    }
    
    cout << sz(ans) << "\n";
    sort(all(ans));
    for (int i: ans) 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: 25 / 100