Submission #54919

#	Time	Username	Problem	Language	Result	Execution time	Memory
54919		dfistric	Printed Circuit Board (CEOI12_circuit)	C++14	10 / 100	478 ms	8956 KiB

circuit

#include <bits/stdc++.h>

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

using namespace std;

const int MAXN = 100010;

struct line {
  point A, B;
};

line lines[MAXN];
point ray;
set <line> s;
vector <point> ve;
vector <int> out;
int arr[MAXN];
int n;
const ld eps = 1e-8;

int ccw(point a, point b, point c) {
  ld out = ((ld) a.X * (b.Y - c.Y)) +
           ((ld) b.X * (c.Y - a.Y)) +
           ((ld) c.X * (a.Y - b.Y));
  if (out > 0.0) return  1;
  if (out < 0.0) return -1;
  return 0;
}

int ccw0(point a, point b) {
  return ccw({0, 0}, a, b);
}

ld dist(point a) {
  return (a.X * a.X) + (a.Y * a.Y);
}

point inter(line a, line b) {
  ld ka = (a.A.Y - a.B.Y) / (a.A.X - a.B.X + eps);
  ld kb = (b.A.Y - b.B.Y) / (b.A.X - b.B.X + eps);
  ld la = a.A.Y - a.A.X * ka;
  ld lb = b.A.Y - b.A.X * kb;

  if (fabs(ka - kb) <= eps && fabs(la - lb) <= eps) {
    if (dist(a.A) < dist(a.B)) return a.A;
    return a.B;
  }

  ld x = (lb - la) / (ka - kb + eps);

  return {x, ka * x + la};
}

bool operator< (const line &x, const line &y) {
  point a = x.A, b = x.B;
  point c = y.A, d = y.B;

  if (ccw0(a, b) < 0) swap(a, b);
  if (ccw0(c, d) < 0) swap(c, d);

  if (ccw(a, b, c) <= 0 && ccw(a, b, d) <= 0) return 1;
  if (ccw(a, b, c) >= 0 && ccw(a, b, d) >= 0) return 0;

  point ix = inter({a, b}, {{0, 0}, ray});
  point iy = inter({c, d}, {{0, 0}, ray});

  ld dx = dist(ix);
  ld dy = dist(iy);

  return dx < dy;
}

bool cmp(int aa, int bb) {
  point a = ve[aa];
  point b = ve[bb];

  if (ccw0(a, b) == 0) {
    ld da = dist(a);
    ld db = dist(b);

    return da < db;
  }
  return ccw0(a, b) > 0;
}

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

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

  sort(arr, arr + n, cmp);

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

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

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

    ld dx = dist(x), dy = 1e13;
    if (s.size()) {
      line tr = *s.begin();
      point y = inter(tr, {{0, 0}, ray});
      dy = dist(y);
    }

    if (dx - dy <= 0.0001) {
      out.push_back(i);
    }

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

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

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

  return 0;
}

• Subtask 1: 10 / 100