Submission #1281146

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281146		jy0n	Printed Circuit Board (CEOI12_circuit)	C++17	10 / 100	23 ms	3620 KiB

circuit

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using iter_t = list<int>::iterator;

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) { 
    //cout << "    Comparing Deg(" << lhs.x << "," << lhs.y << ") < Deg(" << rhs.x << "," << rhs.y << ")\n";
    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) { return (lhs.x-x)*(rhs.y-y)-(lhs.y-y)*(rhs.x-x);}
} p[__];

struct Seg {
  vector<int> data;
  Seg *prev;
  bool inc;
  int dup;

  /*
  void print() {
    cout << "  Seg " << (inc? "inc":"dec") << ": [";
    for (auto v : data) cout << (v+1) << ' ';
    cout << "]\n";
  }
  */
  Seg (bool inc) : prev(nullptr), inc(inc), dup(0) { }
  void pop_back() { data.pop_back(); }
  bool push_back(int v) {
    if (!data.size()) {
      //cout << "    Empty seg, adding " << (v+1) << '\n';
      data.push_back(v);
      return true;
    }
    auto last = data.back();
    auto _th = p[v].deg(), th = p[last].deg();
    auto _d = p[v].dist2(), d = p[last].dist2();
    auto cmp_th = [&]() { return inc? th < _th : _th < th; };
    if (dup) {
      if (cmp_th()) {
        int v0 = data[data.size()-2], v1 = data.back();
        data.pop_back(); data.pop_back();
        data.push_back(dup==1? v1 : v0);
        data.push_back(v);
        dup = 0;
        return true;
      }
      if (dup==1) {
        int v0 = data.back();
        data.pop_back(); data.pop_back();
        data.push_back(v0);
        return false;
      }
      return true;
    } else if (th == _th) {
      dup = d < _d ? 1 : 2;
      data.push_back(v);
      return true;
    }
    if (!cmp_th()) {
      if (data.size()>1 && (inc? p[data[0]].deg() < _th : _th < p[data[0]].deg()) && d < _d) {
        //cout << "    Hiding " << (v+1) << " due to angle\n";
        return true;
      }
      //cout << "    Failed to add " << (v+1) << " due to angle\n";
      return false;
    }
    //cout << "    Adding " << (v+1) << '\n';
    data.push_back(v);
    //print();
    return true;
  }
};

struct SegList {
  Seg *head;
  bool inc;
  SegList (bool inc): inc(inc) { head = new Seg(inc); }
  int back() { return head->data.back(); }
  bool empty() {
    return head==nullptr || head->data.size()==0;
  }

  /*
  void print() {
    cout << "SegList " << (inc? "inc":"dec") << ":\n";
    for (Seg *cur = head; cur!=nullptr; cur=cur->prev) {
      cur->print();
    }
  } 
  */
  bool operator > ( const Point& pt ) const {
    return head->data.size()>0 && 
      (inc ? pt < p[head->data.back()] : p[head->data.back()] < pt);
  }
  void pop_back(bool remove_empty=true) {
    head->data.pop_back();
    if (!head->data.size() && remove_empty) {
      Seg *old = head;
      head = head->prev;
      delete old;
    }
  }
  bool push_back(int v, bool make_seg=false) {
    //cout << "  Pushing " << (v+1) << " to seglist " << (inc? "inc":"dec") << '\n';
    if (!make_seg) return head->push_back(v);
    Seg *x = new Seg(inc);
    x->prev = head;
    head = x;
    return head->push_back(v);
  }
  vector<int> to_vector() {
    vector<int> res;
    for (Seg *cur = head; cur!=nullptr; cur=cur->prev) {
      for (int i=0; i<(int)cur->data.size(); ++i) {
        res.push_back(cur->data[i]);
      }
    }
    return res;
  }
};

struct Circuit {
  SegList seg[2] = {SegList(true), SegList(false)};

  int i;
  Circuit() : i(0) { }
  void add(int v) {
    if (seg[0].empty() && seg[1].empty()) {
      seg[i].push_back(v);
      //cout << "  Initial add\n";
      return;
    }
    if (!seg[i].push_back(v)) {
      //cout << "  Failed to add to seg " << (i? "inc":"dec") << '\n';
      if (!seg[!i].empty()) {
        //cout << "  Adjusting other seg " << (i? "dec":"inc") << '\n';
        int l = seg[!i].back(); seg[!i].pop_back(false);
        ///cout << "    Popped back : " << (l+1) << '\n';
        //seg[!i].print();
        while(seg[!i] > p[seg[i].back()]) {

          seg[!i].pop_back();
          //cout << "    Popped back to adjust\n";
          //seg[!i].print();
        }
        seg[!i].push_back(l);
        if (!(seg[!i] > p[v])) 
        { 
          //cout << "  Removing last from other seg\n";
          seg[!i].pop_back();
          //seg[!i].print();
        }
      }
      //cout << "  Switching seg\n";
      seg[!i].push_back(v, true);
      i = !i;
      //seg[0].print();
      //seg[1].print();
    }
  }
  vector<int> to_vector() {
    vector<int> res;
    for (int k=0; k<2; ++k) {
      auto vk = seg[k].to_vector();
      res.insert(res.end(), vk.begin(), vk.end());
    }
    return res;
  } 

};

int main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cin >> n;
  int max_i, min_i;
  Point max_pt = {1, 0}, min_pt = {0, 1};
  for (int i=0; i<n; ++i) {
    cin >> p[i].x >> p[i].y;
    if (max_pt<p[i]) { max_pt = p[i]; max_i = i; }
    if (p[i]<min_pt) { min_pt = p[i]; min_i = i; }
  }

  Circuit circ = Circuit();
  int di = min_pt.ccw(p[(min_i+1)%n],p[(min_i-1+n)%n])>0? -1 : 1;

  auto next = [&](int i) { return (i+di+n)%n; };

  for (int i=min_i,_break=0; !_break; i=next(i)) {
    if (!_break&&i==max_i) ++_break;
    //cout << "Adding point " << i << " (" << p[i].x << "," << p[i].y << ")\n";
    circ.add(i);
  }

  auto vi = circ.to_vector();
  sort(vi.begin(), vi.end());
  cout << vi.size() << '\n';
  for (auto v : vi) cout << (v+1) << ' ';
  cout << '\n';
}

• Subtask 1: 10 / 100