Submission #1280880

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280880		jy0n	Printed Circuit Board (CEOI12_circuit)	C++17	0 / 100	98 ms	3532 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);
  }
  ll ccw(const Point& lhs, const Point& rhs) const {
    return (lhs.x-x)*(rhs.y-y)-(lhs.y-y)*(rhs.x-x);
  } 
} p[__];

void merge(stack<int>& st, stack<int>& tmp) {
  if (!tmp.size()) return;  
  while (p[tmp.top()].deg()<=p[st.top()].deg() ) {
    //cout << " merge " << (tmp.top()+1) << " pop " << (st.top()+1) << '\n';
    st.pop();
  }
  while (tmp.size()) {
    //cout  << " push- " << (tmp.top()+1) << '\n';
    st.push(tmp.top());
    tmp.pop();
  }
}

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, tmp;
  st.push(mi);
  int dir=1, di = m.ccw(p[(mi+1)%n],p[(mi-1+n)%n])>0? -1 : 1;
  
  for (int i=(mi+di+n)%n,flag=1; flag; i=(i+di+n)%n) {
    if (flag&&i==Mi) flag=0;
    //cout << "i=" << (i+1) << " stsize=" << st.size() << '\n';
    auto degi = p[i].deg(), degt = p[st.top()].deg();
    auto Li = p[i].dist2(), Lt = p[st.top()].dist2();
    if (degi==degt) { continue; }
    if (st.size()<2) {
      //cout  << " push0 " << (i+1) << '\n';
      st.push(i);
      continue;
    }

    int ndir = degi<degt? -1 : 1;
    if (dir*ndir<0&&Li<=Lt) {

      merge(st, tmp);
      Lt = p[st.top()].dist2();
      degt = p[st.top()].deg();

      //cout << "tmp push " << (i+1) << '\n';
      tmp.push(i);
      
      
    } else if (dir*ndir>0) {
      //cout  << " push+" << (i+1) << '\n';
      st.push(i);
    } 
  }
  merge(st, tmp);
  st.push(Mi);
  vector<int> ans;
  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: 0 / 100