Submission #567048

#	Time	Username	Problem	Language	Result	Execution time	Memory
567048		600Mihnea	The Forest of Fangorn (CEOI14_fangorn)	C++17	0 / 100	3066 ms	732 KiB

fangorn

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Vector {
  ll x;
  ll y;



  /**Vector() : x(0), y(0) {
  }

  Vector(ll x, ll y) : x(x), y(y) {

  }*/
};

Vector operator + (Vector a, Vector b) {
  return {a.x+b.x, a.y+b.y};
}

Vector operator - (Vector a, Vector b) {
  return {a.x-b.x, a.y-b.y};
}

Vector operator * (Vector a, ll b) {
  return {a.x*b, a.y*b};
}


Vector operator * (ll b, Vector a) {
  return {a.x*b, a.y*b};
}


Vector readVector() {
  int x,y;
  cin>>x>>y;
  return {x, y};
}

const int N=2000+7;
const int C=10000+7;

int n,c;
Vector camps[C];
Vector trees[N];
Vector myself;

bool cmpByAngle(Vector a,Vector b) {
  return atan2(a.y, a.x)<atan2(b.y, b.x);
}

bool cmp(pair<Vector, int> a, pair<Vector, int> b) {
  return cmpByAngle(a.first, b.first);
}

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);

  {
    int _, __;
    cin>>_>>__;
  }
  myself=readVector();

  cin>>c;
  vector<int> sol;
  for (int i=1;i<=c;i++) {
    camps[i]=readVector();
    sol.push_back(i);
  }
  cin>>n;
  for (int i=1;i<=n;i++) {
    trees[i]=readVector();
  }
  for (int tid=1;tid<=n;tid++) {
   /// tid=3;
    Vector origin=trees[tid];
    vector<pair<Vector,int>> events;
    for (int i=1;i<=n;i++) {
      if (i==tid) continue;
      Vector delta=trees[i]-origin;
      events.push_back({{-delta.x,-delta.y}, -1});
    }
    for (auto &i : sol) {
      events.push_back({camps[i]-origin, i});
    }
    events.push_back({myself-origin, 0});
    sort(events.begin(), events.end(),cmp);
    int p0=0;
    while (events[p0].second!=0) p0++;
    assert(p0<(int)events.size());
    assert(events[p0].second==0);
    int l=p0,r=p0,sz=(int)events.size();

    while (events[(l+sz-1)%sz].second!=-1) l=(l+sz-1)%sz;
    while (events[(r+1)%sz].second!=-1) r=(r+1)%sz;

    vector<int> ns;

    for (int j=l;j!=(r+1)%sz;j=(j+1)%sz) {
      assert(events[j].second>=0);
      if (events[j].second>0) {
        ns.push_back(events[j].second);
        assert(1<=events[j].second&&events[j].second<=c);
      }
    }
    sol=ns;
  }
  cout<<(int)sol.size()<<"\n";
  for (auto &i:sol) {
    cout<<i<<" ";
  }
  cout<<"\n";
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 20