oj.uz

답안 #567113

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
567113 2022-05-23T08:09:48 Z 600Mihnea The Forest of Fangorn (CEOI14_fangorn) C++17
50 / 100
 3000 ms 724 KB 
#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

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.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 12 ms 340 KB Output is correct
8 Correct 13 ms 332 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 212 KB Output is correct
2 Correct 6 ms 344 KB Output is correct
3 Correct 12 ms 344 KB Output is correct
4 Correct 16 ms 340 KB Output is correct
5 Correct 19 ms 340 KB Output is correct
6 Correct 51 ms 328 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 268 KB Output is correct
9 Correct 11 ms 340 KB Output is correct
10 Correct 98 ms 340 KB Output is correct
11 Correct 117 ms 340 KB Output is correct
12 Correct 123 ms 360 KB Output is correct

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 4 ms 212 KB Output is correct
3 Correct 5 ms 324 KB Output is correct
4 Execution timed out 3077 ms 468 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3078 ms 724 KB Time limit exceeded
2 Halted 0 ms 0 KB -