Submission #1236204

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236204		abc864197532	Printed Circuit Board (CEOI12_circuit)	C++20	70 / 100	184 ms	61036 KiB

circuit

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define pb push_back
#define all(a) a.begin(), a.end()
#define sz(a) ((int)a.size())
#ifdef Doludu
template <typename T>
ostream& operator << (ostream &o, vector <T> vec) {
    o << "{"; int f = 0;
    for (T i : vec) o << (f++ ? " " : "") << i;
    return o << "}";
}
void bug__(int c, auto ...a) {
    cerr << "\e[1;" << c << "m";
    (..., (cerr << a << " "));
    cerr << "\e[0m" << endl;
}
#define bug_(c, x...) bug__(c, __LINE__, "[" + string(#x) + "]", x)
#define bug(x...) bug_(32, x)
#define bugv(x...) bug_(36, vector(x))
#define safe bug_(33, "safe")
#else
#define bug(x...) void(0)
#define bugv(x...) void(0)
#define safe void(0)
#endif
const int mod = 998244353, N = 500005;

int sign(ll x) { return clamp(x, -1ll, 1ll); }
template <typename T> struct P {
  T x, y;
  P (T _x = 0, T _y = 0) : x(_x), y(_y) {}
  P<T> operator + (P<T> o) {
    return P<T>(x + o.x, y + o.y);}
  P<T> operator - (P<T> o) {
    return P<T>(x - o.x, y - o.y);}
  P<T> operator * (T k) {return P<T>(x * k, y * k);}
  P<T> operator / (T k) {return P<T>(x / k, y / k);}
  T operator * (P<T> o) {return x * o.x + y * o.y;}
  T operator ^ (P<T> o) {return x * o.y - y * o.x;}
  friend ostream& operator << (ostream &o, P<T> a) {
    return o << "(" << a.x << ", " << a.y << ")"; }
  bool operator == (P<T> o) {
    return sign(x - o.x) == 0 && sign(y - o.y) == 0;}
};
using Pt = P<ll>;
struct Line {
    Pt a, b;
};

int ori(Pt o, Pt a, Pt b) {
    return sign((o - a) ^ (o - b));
}
ll abs2(Pt o) {
    return o * o;
}

struct Event {
    Pt d; int type;
    Line ls;
    bool operator < (const Event &o) {
        if ((d ^ o.d) == 0) return type < o.type;
        return (d ^ o.d) > 0;
    }
};

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n; cin >> n;
    vector <Pt> pts(n);
    for (int i = 0; i < n; ++i) {
        cin >> pts[i].x >> pts[i].y;
    }
    vector <Event> eve;
    // -1 -> insert, [0, n) -> query, n -> delete
    for (int i = 0; i < n; ++i) {
        int ni = i + 1 == n ? 0 : i + 1;
        Pt a = pts[i], b = pts[ni];
        if (sign(a ^ b) < 0) swap(a, b);
        else if (sign(a ^ b) == 0 && abs2(b) < abs2(a)) swap(a, b);
        eve.pb({a, -1, Line{a, b}});
        eve.pb({b, n, Line{a, b}});
        eve.pb({pts[i], i, Line{pts[i], pts[i]}});
    }
    sort(all(eve));
    auto cmp = [&](Line a, Line b) {
        if (a.a == b.a) {
            int x = ori(b.b, a.a, a.b);
            if (x) return x == -1;
            return false;
        } else if ((a.a ^ b.a) > 0) {
            assert((a.a ^ a.b) > 0);
            int x = ori(b.a, a.a, a.b);
            if (x) return x == -1;
            x = ori(b.b, a.a, a.b);
            assert(x);
            return x == -1;
        } else {
            assert((b.a ^ b.b) > 0);
            int x = ori(a.a, b.a, b.b);
            if (x) return x == 1;
            x = ori(a.b, b.a, b.b);
            assert(x);
            return x == 1;
        }
    };
    set <Line, decltype(cmp)> S(cmp);
    vector <int> ans;
    for (auto [d, type, l] : eve) {
        if (type == -1) {
            S.insert(l);
        } else if (type == n) {
            S.erase(l);
        } else {
            assert(!S.empty());
            auto [a, b] = *S.begin();
            if (a == pts[type] || b == pts[type]) {
                if (sign(a ^ b) == 0 && b == pts[type]) continue;
                ans.pb(type);
            }
        }
    }
    sort(all(ans));
    cout << sz(ans) << "\n";
    for (int i = 0; i < sz(ans); ++i) cout << ans[i] + 1 << " \n"[i + 1 == sz(ans)];
}

• Subtask 1: 70 / 100