Submission #567042

#	Time	Username	Problem	Language	Result	Execution time	Memory
567042		600Mihnea	The Forest of Fangorn (CEOI14_fangorn)	C++17	0 / 100	3 ms	400 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;
int cnt_good[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);

  freopen ("input.txt", "r", stdin);

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

  cin>>c;
  for (int i=1;i<=c;i++) {
    camps[i]=readVector();
  }
  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;
      /// trees[i] - origin = delta
      /// trees[i] = origin + delta
      events.push_back({{-delta.x,-delta.y}, -1});
    }
    for (int i=1;i<=c;i++) {
      events.push_back({camps[i]-origin, i});
    }
    events.push_back({myself-origin, 0});
    sort(events.begin(), events.end(),cmp);
    int cox=0;
    /*cout<<"0 0 O\n";
    for (auto &it : events) {
      cox++;

      cout<<it.first.x<<" "<<it.first.y<<" P";
      if (it.second==-1) {
        cout<<"x";
      }else{
        cout<<it.second;

      }
      cout<<"\n";
    }*/
    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;

    /*
    for (auto &j : events) {
      cout<<j.second<<" ";
    }
    cout<<" -------> ";

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

Compilation message (stderr)

fangorn.cpp: In function 'int main()':
fangorn.cpp:97:9: warning: unused variable 'cox' [-Wunused-variable]
   97 |     int cox=0;
      |         ^~~
fangorn.cpp:65:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |   freopen ("input.txt", "r", stdin);
      |   ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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