제출 #226304

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
226304		Bruteforceman	Printed Circuit Board (CEOI12_circuit)	C++11	10 / 100	1097 ms	5240 KiB

circuit

#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 / 100