oj.uz

답안 #54919

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
54919 2018-07-05T11:36:23 Z dfistric Printed Circuit Board (CEOI12_circuit) C++14
10 / 100
 100 ms 8956 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 <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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Incorrect 5 ms 492 KB Output isn't correct
3 Correct 11 ms 948 KB Output is correct
4 Correct 14 ms 1152 KB Output is correct
5 Incorrect 35 ms 1224 KB Output isn't correct
6 Incorrect 32 ms 1224 KB Output isn't correct
7 Incorrect 68 ms 1968 KB Output isn't correct
8 Incorrect 23 ms 1968 KB Output isn't correct
9 Incorrect 30 ms 1968 KB Output isn't correct
10 Incorrect 32 ms 1968 KB Output isn't correct
11 Incorrect 37 ms 1968 KB Output isn't correct
12 Incorrect 57 ms 1968 KB Output isn't correct
13 Execution timed out 131 ms 2576 KB Time limit exceeded
14 Execution timed out 130 ms 5380 KB Time limit exceeded
15 Execution timed out 157 ms 5380 KB Time limit exceeded
16 Execution timed out 347 ms 5380 KB Time limit exceeded
17 Execution timed out 478 ms 6916 KB Time limit exceeded
18 Runtime error 57 ms 8104 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 43 ms 8888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 45 ms 8956 KB Execution killed with signal 11 (could be triggered by violating memory limits)