Submission #567113

#	Time	Username	Problem	Language	Result	Execution time	Memory
567113		600Mihnea	The Forest of Fangorn (CEOI14_fangorn)	C++17	50 / 100	3078 ms	724 KiB

fangorn

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

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 w,h;
int n,c;
int cnt_good[C];
Vector camps[C];
Vector trees[N];
Vector myself;

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

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

int get_type(Vector a) {
  assert(a.x==0||a.x==w||a.y==0||a.y==h);

  if (a.x==w) return 0;
  if (a.y==h) return 1;
  if (a.x==0) return 2;
  if (a.y==0) return 3;
  assert(0);
}

bool cmpOnRect(int i,int j) {
  Vector a=camps[i];
  Vector b=camps[j];

  int type_a=get_type(a);
  int type_b=get_type(b);
  if (type_a!=type_b) return type_a<type_b;
  int type=type_a;

  if (type==0) {
    assert(a.y!=b.y);
    return a.y<b.y;
  }
  if (type==1) {
    assert(a.x!=b.x);
    return a.x>b.x;
  }
  if (type==2) {
    assert(a.y!=b.y);
    return a.y>b.y;
  }
  if (type==3) {
    assert(a.x!=b.x);
    return a.x<b.x;
  }
  assert(0);
}

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

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

  cin>>w>>h;
  myself=readVector();

  vector<int> inds;

  cin>>c;
  for (int i=1;i<=c;i++) {
    camps[i]=readVector();
    inds.push_back(i);
  }
  sort(inds.begin(), inds.end(), cmpOnRect);

  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});
    }
    events.push_back({myself-origin, 0});
    auto cop_events=events;
    for (int i=1;i<=c;i++) {
      events.push_back({camps[i]-origin, i});
    }
    assert((int)inds.size()==c);

    ld minAng=(ld)1e18;
    int start=-1;

    for (int P=0;P<c;P++) {
      int i=inds[P];
      Vector vec=camps[i]-origin;
      ld ang=atan2(vec.y,vec.x);
      if (ang<minAng) {
        minAng=ang;
        start=P;
      }
    }
    assert(start!=-1);

    vector<pair<Vector, int>> cps;
    for (int l=0;l<c;l++) {
      int i=inds[(start+l)%c];
      cps.push_back({camps[i] - origin, i});
    }

    sort(cop_events.begin(), cop_events.end(), cmp);
    sort(cps.begin(), cps.end(), cmp);
    vector<pair<Vector, int>> so;

    /// so = mrg(cps, cop_events)

    int p1=0, p2=0;
    while (p1<(int)cps.size()&&p2<(int)cop_events.size()) {
      if (cmp(cps[p1], cop_events[p2])) {
        so.push_back(cps[p1++]);
      } else{
        so.push_back(cop_events[p2++]);
      }
    }
    while (p1<(int)cps.size()) {
      so.push_back(cps[p1++]);
    }

    while(p2<(int)cop_events.size()) {
      so.push_back(cop_events[p2++]);
    }

    sort(events.begin(), events.end(),cmp);
    if (0) {
      for (auto &it : so) cout<<it.second<<" "; cout<<"\n";
      for (auto &it : events) cout<<it.second<<" "; cout<<"\n\n";

      for (int i=0;i<(int)so.size();i++) {
        cout<<so[i].first.x<<" "<<so[i].first.y<<" P"<<i<<"\n";
      }
      for (int i=0;i<(int)events.size();i++) {
        cout<<events[i].first.x<<" "<<events[i].first.y<<" P"<<i<<"\n";
      }
      exit(0);
    }
    events=so;
    /**cout<<"\t\t\t\t";
    for (int i=1;i<=c;i++) {
      cout<<cnt_good[i]<<" ";
    }
    cout<<"\n";
    events=so;**/
    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:185:7: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  185 |       for (auto &it : so) cout<<it.second<<" "; cout<<"\n";
      |       ^~~
fangorn.cpp:185:49: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  185 |       for (auto &it : so) cout<<it.second<<" "; cout<<"\n";
      |                                                 ^~~~
fangorn.cpp:186:7: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  186 |       for (auto &it : events) cout<<it.second<<" "; cout<<"\n\n";
      |       ^~~
fangorn.cpp:186:53: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  186 |       for (auto &it : events) cout<<it.second<<" "; cout<<"\n\n";
      |                                                     ^~~~
fangorn.cpp:203:9: warning: unused variable 'cox' [-Wunused-variable]
  203 |     int cox=0;
      |         ^~~

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