Submission #115158

#	Time	Username	Problem	Language	Result	Execution time	Memory
115158		Nnandi	Printed Circuit Board (CEOI12_circuit)	C++14	80 / 100	315 ms	16492 KiB

circuit

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct Pont {
    ll x, y;
    int id;
    void olvas(int i) {
        id = i;
        cin>>x>>y;
    }
    bool operator== (Pont masik) {
        return id == masik.id;
    }
};

Pont vec(Pont a, Pont b) {
    b.x -= a.x;
    b.y -= a.y;
    return b;
}

int sgn(ll exp) {
    if(0LL < exp) return 1;
    if(exp < 0LL) return -1;
    return 0;
}

int Irany(Pont o, Pont a, Pont b) {
    a = vec(o,a);
    b = vec(o,b);
    ll cp = a.x * b.y - a.y * b.x;
    return sgn(cp);
}

bool Kozte(Pont a, Pont b, Pont c) {
    a = vec(b,a);
    c = vec(b,c);
    if(sgn(a.x) == -sgn(c.x) && sgn(a.x) != 0) return true;
    if(sgn(a.y) == -sgn(c.y) && sgn(a.y) != 0) return true;
    return false;
}

Pont sp;

bool kisebb(Pont p, Pont q) {
    int dir = Irany(sp,p,q);
    if(dir != 0) {
        return dir == 1;
    }
    return Kozte(sp,p,q);
}

struct Szak{
    Pont a, b;
    Szak() { }
    Szak(Pont aa, Pont bb) {
        a = aa;
        b = bb;
    }
    const bool operator< (Szak M) const {
        if(a.id == M.a.id && b.id == M.b.id) return false;
        if(a.id == M.b.id && b.id == M.a.id) return false;
        if(M.a == a) {
            return Irany(M.a,M.b,b) == 1;
        }
        if(M.b == b) {
            return Irany(M.b,M.a,a) == -1;
        }
        if(M.a == b) {
            return a.id < M.b.id;
        }
        if(M.b == a) {
            return b.id < M.a.id;
        }
        if(Irany(a,b,M.a) == 0 && Irany(a,b,M.b) == 0 && Irany(a, b, sp) == 0) {
            if(Kozte(sp,a,M.a) && Kozte(sp,b,M.a)) return true;
            if(Kozte(sp,M.a,a) && Kozte(sp,M.b,a)) return false;
        }
        if(Irany(M.a, M.b, a) == Irany(M.a, M.b, b))    return Irany(M.a, M.b, a) == 1;
        if(Irany(a,b,M.a) == Irany(a,b,M.b))    return Irany(a, b, M.a) == -1;
        return false;
    }
};


const int maxn = 200005;
int n;
Pont t[maxn];
Pont v[maxn];
bool sol[maxn];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n;
    for(int i=1;i<=n;i++) {
        t[i].olvas(i);
        v[i] = t[i];
    }
    t[n+1] = t[1];
    t[0] = t[n];
    sort(v+1,v+n+1,kisebb);
    set<Szak> H;

    for(int i=1;i<=n;i++) {
        int idj = v[i].id;

        if(Irany(sp,t[idj],t[idj+1]) >= 0) {
            Szak uj(t[idj],t[idj+1]);
            H.insert(uj);
        }
        if(Irany(sp,t[idj],t[idj-1]) >= 0) {
            Szak uj(t[idj],t[idj-1]);
            H.insert(uj);
        }

        Szak k = *H.begin();

        int dir = Irany(sp,k.a,k.b);
        if(dir == 0 && k.a.id == idj && Kozte(sp,k.a,k.b)) sol[idj] = true;
        if(dir == 0 && k.b.id == idj && Kozte(sp,k.b,k.a)) sol[idj] = true;
        if(dir != 0 && k.a.id == idj) sol[idj] = true;
        if(dir != 0 && k.b.id == idj) sol[idj] = true;

        if(Irany(sp,t[idj],t[idj+1]) <= 0) {
            Szak re(t[idj+1],t[idj]);
            H.erase(re);
        }
        if(Irany(sp,t[idj],t[idj-1]) <= 0) {
            Szak re(t[idj-1],t[idj]);
            H.erase(re);
        }
    }
    int db = 0;
    for(int i=1;i<=n;i++) {
        if(sol[i]) db++;
    }
    cout<<db<<endl;
    for(int i=1;i<=n;i++) {
        if(sol[i]) {
            cout<<i<<" ";
        }
    }
    cout<<endl;
    return 0;
}

• Subtask 1: 80 / 100