oj.uz

Submission #567172

# Submission time Handle Problem Language Result Execution time Memory
567172 2022-05-23T08:48:30 Z 600Mihnea The Forest of Fangorn (CEOI14_fangorn) C++17
50 / 100
 977 ms 556 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double ld;

struct Vector {
  ll x;
  ll y;
};

ll f(Vector a, Vector b) {
  return (a.x - b.x) * (ll) (a.y + b.y);
}

ll f(Vector a, Vector b, Vector c) {
  return f(a, b) + f(b, c) + f(c, a);
}

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;

const ld eps=1e-14;

bool cmp(pair<Vector, int> a, pair<Vector, int> b) {
  return atan2((ld)a.first.y, (ld)a.first.x) - atan2((ld)b.first.y, (ld)b.first.x)<eps;
}

int get_type(Vector a) {

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

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) {
    return a.y < b.y;
  }
  if (type == 1) {
    return a.x > b.x;
  }
  if (type == 2) {
    return a.y > b.y;
  }
  if (type == 3) {
    return a.x < b.x;
  }
}

ld get_f(pair<ld, ld> a, pair<ld, ld> b) {
  return (a.first - b.first) * (a.second + b.second);
}

ld get_f(pair<ld, ld> a, pair<ld, ld> b, pair<ld, ld> c) {
  return get_f(a, b) + get_f(b, c) + get_f(c, a);
}

int get_cadran(pair<ld, ld> a) {
  if (a.first >= 0) {
    if (a.second >= 0) {
      return 0;
    } else {
      return 3;
    }
  } else {
    if (a.second <= 0) {
      return 2;
    } else {
      return 1;
    }
  }
}

int tr_cadran(int c) {
  return (c + 2) % 4;
}

bool cmp_pld(pair<ld, ld> a, pair<ld, ld> b) {
  int cadran_a = get_cadran(a);
  int cadran_b = get_cadran(b);
  cadran_a = tr_cadran(cadran_a);
  cadran_b = tr_cadran(cadran_b);
  if (cadran_a != cadran_b) {
    return cadran_a < cadran_b;
  }
  return (get_f(pair<ld, ld> (0, 0), a, b) > 0);
}



int get_cadran(Vector a) {
  if (a.x >= 0) {
    if (a.y > 0) {
      return 0;
    } else {
      return 3;
    }
  } else {
    if (a.y < 0) {
      return 2;
    } else {
      return 1;
    }
  }
}

bool cmp_Vector(Vector a, Vector b) {
  int cadran_a = get_cadran(a);
  int cadran_b = get_cadran(b);
  cadran_a = tr_cadran(cadran_a);
  cadran_b = tr_cadran(cadran_b);
  if (cadran_a != cadran_b) {
    return cadran_a < cadran_b;
  }
  return (f({0, 0}, a, b) > 0);
}

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

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

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


  if (0) {
    const int cntc=16;

    vector<pair<ld, ld>> all;
    for (int j=0;j<cntc;j++) {
      const ld pi=(ld)2*acos((ld)0);
      ld x=cos((ld)j/cntc*(2*pi));
      ld y=sin((ld)j/cntc*(2*pi));
      all.push_back({x, y});
     // cout<<x<<" "<<y<<" P"<<j<<"\n";
    }
    sort(all.begin(), all.end(), cmp_pld);
    for (int i = 0; i < (int) all.size(); i++) {
      ld x = all[i].first, y = all[i].second;
      cout << x << " " << y << " P" << i << "\n";
    }
    exit(0);
  }

  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();
  }

  bool is = (n >= 1500);


  for (int tid = 1; tid <= n; tid++) {
    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 });
    }
    events.push_back({ myself - origin, 0 });


    auto cop_events = events;

    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;
      }
    }

    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 });
    }



    if (is) {
      continue;
    }
    auto cop_events2 = cop_events;

    sort(cop_events.begin(), cop_events.end(), cmp);
    sort(cop_events2.begin(), cop_events2.end(), cmp2);

    if (0) {
      for (auto &it : cop_events) cout << it.second << " "; cout << "\n";
      for (auto &it : cop_events2) cout << it.second << " "; cout << "\n";
      cout << "\n";
    }

    if (1 && (tid == -3)) {
      int cnt = 1;
      cout << 0 << " " << 0 << " O\n";
      for (auto &it : cop_events2) {
        cout << it.first.x << " " << it.first.y << " P" << cnt++ << "\n";
      }
      cout << "-------------\n";

      return 0;
    }

    if (tid == 1 || tid == 2 || 1) {
      cop_events = cop_events2;
    }

    vector<pair<Vector, int>> so;

    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++]);
    }

    events = so;
    int p0 = 0;
    while (events[p0].second != 0) p0++;

    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 (int j = l; j != (r + 1) % sz; j = (j + 1) % sz) {
      if (events[j].second > 0) {
        cnt_good[events[j].second]++;
      }
    }
  }
  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:252:7: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  252 |       for (auto &it : cop_events) cout << it.second << " "; cout << "\n";
      |       ^~~
fangorn.cpp:252:61: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  252 |       for (auto &it : cop_events) cout << it.second << " "; cout << "\n";
      |                                                             ^~~~
fangorn.cpp:253:7: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  253 |       for (auto &it : cop_events2) cout << it.second << " "; cout << "\n";
      |       ^~~
fangorn.cpp:253:62: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  253 |       for (auto &it : cop_events2) cout << it.second << " "; cout << "\n";
      |                                                              ^~~~
fangorn.cpp: In function 'int get_type(Vector)':
fangorn.cpp:67:1: warning: control reaches end of non-void function [-Wreturn-type]
   67 | }
      | ^
fangorn.cpp: In function 'bool cmpOnRect(int, int)':
fangorn.cpp:90:1: warning: control reaches end of non-void function [-Wreturn-type]
   90 | }
      | ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 4 ms 340 KB Output is correct
8 Correct 3 ms 340 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 6 ms 340 KB Output is correct
5 Correct 5 ms 340 KB Output is correct
6 Correct 15 ms 360 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 5 ms 340 KB Output is correct
10 Correct 29 ms 340 KB Output is correct
11 Correct 30 ms 372 KB Output is correct
12 Correct 35 ms 372 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 977 ms 468 KB Output is correct
5 Correct 191 ms 388 KB Output is correct
6 Incorrect 70 ms 488 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 167 ms 556 KB Output isn't correct
2 Halted 0 ms 0 KB -