Submission #54999

#	Time	Username	Problem	Language	Result	Execution time	Memory
54999		dfistric	Printed Circuit Board (CEOI12_circuit)	C++14	80 / 100	149 ms	6076 KiB

circuit

#include <bits/stdc++.h>

#define FOR(i, a, b) for(ll i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define poll pair <ll, ll>
#define X first
#define Y second
#define ll long long

using namespace std;

const ll MAXN = 100010;

struct line {
  poll A, B;
};

line lines[MAXN];
poll ray;
multiset <line> s;
vector <poll> ve;
vector <ll> out;
ll arr[MAXN];
int n;

ll ccw(poll a, poll b, poll c) {
  ll out = ((ll) a.X * (b.Y - c.Y)) +
           ((ll) b.X * (c.Y - a.Y)) +
           ((ll) c.X * (a.Y - b.Y));
  return out;
}

ll ccw0(poll a, poll b) {
  return ccw({0, 0}, a, b);
}

ll dist(poll a) {
  return (a.X * a.X) + (a.Y * a.Y);
}

bool operator==(line x, line y) {
  return x.A == y.A && x.B == y.B;
}

bool operator< (line x, line y) {
  if (x == y) return 0;
  if (ccw0(x.A, x.B) < 0) swap(x.A, x.B);
  if (ccw0(y.A, y.B) < 0) swap(y.A, y.B);

  ll P = ccw(x.B, x.A, y.A) + ccw(x.B, y.A, y.B);

  if (P == 0) {
    if (x.A.Y == y.A.Y) return x.A.X < y.A.X;
    return x.A.Y < y.A.Y;
  }

  return P > 0;
}

bool cmp(ll a, ll b) {
  if (ccw0(ve[a], ve[b]) == 0) {
    return ve[a] < ve[b];
  }
  return ccw0(ve[a], ve[b]) > 0;
}

int main() {
  ios_base::sync_with_stdio(false);

  cin >> n;
  REP(i, n) {
    ll a, b;
    cin >> a >> b;
    ve.push_back({a, b});
    arr[i] = i;
  }

  sort(arr, arr + n, cmp);

  REP(ind, n) {
    ll i = arr[ind];
    poll x = ve[i];
    ray = x;

    for (ll t : {-1, 1}) {
      ll j = (i + t + n) % n;
      poll y = ve[j];
      
      if (cmp(i, j)) {
        line tr = {x, y};
        s.insert(tr);
      }
    }

    if (ind == 0 || ccw0(ve[i], ve[arr[ind - 1]]) != 0) {
      line tr = *s.begin();
      if (ccw(tr.A, tr.B, x) == 0) out.push_back(i);
    }

    for (ll t : {-1, 1}) {
      ll j = (i + t + n) % n;
      poll y = ve[j];

      if (!cmp(i, j)) {
        line tr = {y, x};
        s.erase(s.find(tr));
      }
    }
  }

  sort(out.begin(), out.end());
  cout << out.size() << "\n";
  for (ll x : out) cout << x + 1 << " ";
  cout << "\n";

  return 0;
}

• Subtask 1: 80 / 100