Submission #1280848

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280848		jy0n	Printed Circuit Board (CEOI12_circuit)	C++17	5 / 100	89 ms	3452 KiB

circuit

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int __ = 2e5;
int n;
struct Deg {
  ll x, y;
  Deg (ll x, ll y): x(x), y(y) { }
  friend bool operator==(const Deg lhs, const Deg rhs) {
    return  rhs.x*lhs.y==lhs.x*rhs.y ;
  }
  friend bool operator<(const Deg lhs, const Deg rhs) {
    return  rhs.x*lhs.y<lhs.x*rhs.y ;
  };
  friend bool operator<=(const Deg lhs, const Deg rhs) {
    return  rhs.x*lhs.y<=lhs.x*rhs.y ;
  }
};
struct Point {
  ll x, y;
  friend bool operator<(const Point lhs, const Point rhs) {
    ll d1 = lhs.dist2(), d2 = rhs.dist2();
    ll v1 = rhs.x*lhs.y, v2 = lhs.x*rhs.y;
    if (v1==v2) return d1<d2;
    return v1<v2;
  }
  ll dist2() const {
    return x*x+y*y;
  }
  Deg deg() const {
    return Deg(x,y);
  }
} p[__];


int main() {
  //ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cin >> n;
  int Mi, mi;
  Point M = {1, 0}, m = {0, 1};
  for (int i=0; i<n; ++i) {
    cin >> p[i].x >> p[i].y;
    if (M<p[i]) { M = p[i]; Mi = i; }
    if (p[i]<m) { m = p[i]; mi = i; }
  }
  stack<int> st;
  st.push(Mi);
  int dir, di = p[(Mi+1)%n].dist2()>p[(Mi-1+n)%n].dist2()? 1 : -1;
  
  for (int i=mi,flag=0; !flag; i=(i+di+n)%n) {
    if (!flag&&i==Mi) ++flag;
    auto degi = p[i].deg(), degt = p[st.top()].deg();
    auto disti = p[i].dist2(), distt = p[st.top()].dist2();
    if (degi==degt) { continue; }
    if (st.size()<2) { 
      st.push(i); 
      dir = degi<degt? -1 : 1;
      continue;
    }
    int ndir = degi<degt? -1 : 1;
    if (dir*ndir<0 && disti<=distt) {
      int t = st.top(); st.pop();
      while (true) {
        auto d = p[st.top()].deg();
        if (ndir<0&&degi<=d&&d<=degt||ndir>0&&degt<=d&&d<=degi) {
          st.pop();
        } else break;
      }
      st.push(t);
      st.push(i);
      dir = ndir;
    } else if (dir*ndir>0) {
      st.push(i);
    } 
  }
  vector<int> ans;
  st.pop();
  while (st.size()) {
    ans.push_back(st.top()+1);
    st.pop();
  }
  sort(ans.begin(), ans.end());
  cout << ans.size() << '\n';
  for (auto v : ans) cout << v << ' ';
  cout << '\n';
}

• Subtask 1: 5 / 100