oj.uz

Submission #226304

# Submission time Handle Problem Language Result Execution time Memory
226304 2020-04-23T10:51:59 Z Bruteforceman Printed Circuit Board (CEOI12_circuit) C++11
10 / 100
 100 ms 5240 KB 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n;
struct point {
  long long x, y;
  point () {}
  point (long long x, long long y) : x(x), y(y) {}
  point operator + (point p) const {
    return point(x + p.x, y + p.y);
  }
  point operator - (point p) const {
    return point(x - p.x, y - p.y);
  }
} a[maxn];
long long cross(point p, point q) { return p.x * q.y - p.y * q.x; }
long long dot(point p, point q) { return p.x * q.x + p.y * q.y; }
bool inSegment(point a, point b, point c) {
  return cross(c - a, b - a) == 0 && 
    dot(a - b, a - b) >= max(dot(a - c, a - c),  dot(c - b, c - b));
}
int side(point a, point b, point c) { 
  long long x = cross(b - a, c - a);
  if(x > 0) return 1;
  else if (x < 0) return -1;
  else return 0;
}
bool intersect(point a, point b, point c, point d) {
  if(side(a, b, c) * side(a, b, d) == -1 &&
      side(c, d, a) * side(c, d, b) == -1) return true;
  for(auto i : {c, d}) if(inSegment(a, b, i)) return true;
  for(auto i : {a, b}) if(inSegment(c, d, i)) return true;
  return false;
}

int main() { 
  cin >> n;
  for(int i = 0; i < n; i++) {
    cin >> a[i].x >> a[i].y;
  }
  vector <int> res;
  for(int i = 0; i < n; i++) {
    bool bad = false;
    for(int j = 0; j < n; j++) {
      int k = (j + 1) % n;
      if(j == i || k == i) continue;
      if(intersect(a[j], a[k], point(0, 0), a[i])) {
        bad = true;
        break;
      }
    }
    if(!bad) res.emplace_back(i + 1);
  }
  cout << res.size() << endl;
  for(auto i : res) cout << i << " ";
  cout << endl;
  return 0;
}

Subtask #1
10.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 9 ms 384 KB Output is correct
3 Execution timed out 155 ms 448 KB Time limit exceeded
4 Execution timed out 272 ms 728 KB Time limit exceeded
5 Execution timed out 742 ms 652 KB Time limit exceeded
6 Execution timed out 754 ms 760 KB Time limit exceeded
7 Execution timed out 1086 ms 896 KB Time limit exceeded
8 Execution timed out 477 ms 512 KB Time limit exceeded
9 Execution timed out 803 ms 588 KB Time limit exceeded
10 Execution timed out 770 ms 760 KB Time limit exceeded
11 Execution timed out 891 ms 724 KB Time limit exceeded
12 Execution timed out 1084 ms 768 KB Time limit exceeded
13 Execution timed out 1089 ms 1152 KB Time limit exceeded
14 Execution timed out 584 ms 1400 KB Time limit exceeded
15 Execution timed out 1097 ms 1784 KB Time limit exceeded
16 Execution timed out 1091 ms 3064 KB Time limit exceeded
17 Execution timed out 1096 ms 3192 KB Time limit exceeded
18 Runtime error 90 ms 4984 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 92 ms 5028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 94 ms 5240 KB Execution killed with signal 11 (could be triggered by violating memory limits)