oj.uz

Submission #54972

# Submission time Handle Problem Language Result Execution time Memory
54972 2018-07-05T15:25:24 Z dfistric Printed Circuit Board (CEOI12_circuit) C++14
60 / 100
 100 ms 3520 KB 
#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 <int, int>
#define X first
#define Y second
#define ll long long

using namespace std;

const int MAXN = 100010;

struct line {
  point A, B;
};

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

ll ccw(point a, point b, point 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(point a, point b) {
  return ccw({0, 0}, a, b);
}

ll dist(point 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(int a, int 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) {
    int a, b;
    cin >> a >> b;
    ve.push_back({a, b});
    arr[i] = i;
  }

  sort(arr, arr + n, cmp);
  //REP(i, n) cout << arr[i] + 1 << " "; cout << endl;

  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);
      }
    }
    
    line tr = *s.begin();
    if (ccw(tr.A, tr.B, x) == 0) 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(s.find(tr));
      }
    }
  }

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

  return 0;
}

Subtask #1
60.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 3 ms 452 KB Output isn't correct
3 Correct 6 ms 656 KB Output is correct
4 Correct 6 ms 732 KB Output is correct
5 Correct 15 ms 836 KB Output is correct
6 Correct 15 ms 952 KB Output is correct
7 Correct 31 ms 1204 KB Output is correct
8 Correct 11 ms 1204 KB Output is correct
9 Correct 11 ms 1204 KB Output is correct
10 Correct 13 ms 1204 KB Output is correct
11 Correct 14 ms 1204 KB Output is correct
12 Incorrect 19 ms 1204 KB Output isn't correct
13 Correct 40 ms 1412 KB Output is correct
14 Correct 37 ms 1412 KB Output is correct
15 Incorrect 42 ms 1416 KB Output isn't correct
16 Execution timed out 103 ms 2048 KB Time limit exceeded
17 Execution timed out 143 ms 3196 KB Time limit exceeded
18 Runtime error 29 ms 3324 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 47 ms 3480 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 31 ms 3520 KB Execution killed with signal 11 (could be triggered by violating memory limits)