Submission #226596

#	Time	Username	Problem	Language	Result	Execution time	Memory
226596		Bruteforceman	Printed Circuit Board (CEOI12_circuit)	C++11	25 / 100	436 ms	6008 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];
int ord[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;
}
pair <long long, long long> sect(point a, point b, point c) {
  point f = b - a;
  long long p = cross(a, f) * c.x;
  long long q = cross(c, f);
  if(q < 0) { q *= -1; p *= -1; }
  return make_pair(p, q); 
}
point piv;
struct data {
  int i, j;
  data () {}
  data (int i, int j) : i(i), j(j) {}
};
int compare(pair <long long, long long> p, pair <long long, long long> q) {
  if(p.first * q.second != q.first * p.second) {
    return p.first * q.second < q.first * p.second ? -1 : 1;
  } else  return 0;
}
bool operator < (data p, data q) {
  vector <point> v ({a[p.i], a[p.j], a[q.i], a[q.j]});
  sort(v.begin(), v.end(), [&] (point p, point q) { return cross(p, q) > 0; } );
  int e = compare(sect(a[p.i], a[p.j], v[1]), sect(a[q.i], a[q.j], v[1]));
  int g = compare(sect(a[p.i], a[p.j], v[2]), sect(a[q.i], a[q.j], v[2]));
  if(e == 0) return g == -1;
  else return e == -1;
}

int main() { 
  cin >> n;
  for(int i = 0; i < n; i++) {
    cin >> a[i].x >> a[i].y;
    ord[i] = i;
  } 
  auto cmp = [&] (int i, int j) {
      return cross(a[i], a[j]) > 0 || 
        (cross(a[i], a[j]) == 0 && dot(a[i], a[i]) < dot(a[j], a[j])); 
  };
  sort(ord, ord + n, cmp); 

  vector <int> res;
  set <data> can;
  int cur = 0;
  while(cur < n) {
    int x = ord[cur];
    for(int i : {-1, 1}) {
      int y = (x + i + n) % n;
      if(cross(a[x], a[y]) < 0) {
        can.erase(data(y, x));
      }
    }
    piv = a[x];
    if(cur == 0 || cross(a[ord[cur - 1]], a[ord[cur]]) != 0) {
      //cout << "now at " << x + 1 << endl;
      //for(auto g : can) {
       // cout << g.i + 1 << ' ' << g.j + 1 << endl;
      //}
      if(can.empty() || 
          !intersect(point(0, 0), a[x], a[can.begin() -> i], 
            a[can.begin() -> j])) res.emplace_back(x+1);
    }
    for(int i : {-1, 1}) {
      int y = (x + i + n) % n;
      if(cross(a[x], a[y]) > 0) {
        can.insert(data(x, y));
      }
    }
    cur++;
  }
  sort(res.begin(), res.end());
  cout << res.size() << endl;
  for(auto i : res) cout << i << " ";
  cout << endl;
  return 0;
}

• Subtask 1: 25 / 100