oj.uz

Submission #117080

# Submission time Handle Problem Language Result Execution time Memory
117080 2019-06-14T16:15:52 Z IOrtroiii The Forest of Fangorn (CEOI14_fangorn) C++14
100 / 100
 473 ms 768 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

struct Point {
   int x, y;
   Point(int x = 0, int y = 0) : x(x), y(y) {}
   Point operator - (const Point &p) const {
      return Point(x - p.x, y - p.y);
   }
   bool operator < (const Point &p) const {
      return x < p.x || (x == p.x && y < p.y);
   }
   bool operator == (const Point &p) const {
      return x == p.x && y == p.y;
   }
   ll cross(const Point &p) const {
      return (ll) x * p.y - (ll) y * p.x;
   }
};

bool ccw(Point p, Point q) {
   return p.cross(q) > 0;
}

Point org = Point();

void read(Point &p) {
   cin >> p.x >> p.y;
}

const int N = 2020;
const int C = 10100;

int w, h;
int c, n;
Point g;
Point cm[C];
Point tr[N];
bool fail[C];

bool cmp(Point p, Point q) {
   bool fp = org < p;
   bool fq = org < q;
   if (fp ^ fq) {
      return fp;
   } else {
      return ccw(p, q);
   }
}

int main() {
   ios_base::sync_with_stdio(false);
   cin >> w >> h;
   read(g);
   cin >> c;
   for (int i = 1; i <= c; ++i) {
      read(cm[i]);
   }
   cin >> n;
   for (int i = 1; i <= n; ++i) {
      read(tr[i]);
   }
   for (int i = 1; i <= n; ++i) {
      vector<Point> ps;
      Point ng = g - tr[i];
      ps.push_back(ng);
      for (int j = 1; j <= n; ++j) if (j != i) {
         ps.push_back(tr[i] - tr[j]);
      }
      // cout << "At " << i << "\n";
      sort(ps.begin(), ps.end(), cmp);
      /*
      for (auto p : ps) {
         cout << p.x << ' ' << p.y << "\n";
      }
      */
      Point bl, br;
      for (int j = 0; j < n; ++j) {
         if (ng == ps[j]) {
            bl = ps[(j + n - 1) % n];
            br = ps[(j + 1) % n];
            break;
         }
      }
      // cout << "bl :" << bl.x << ' ' << bl.y << "\n";
      // cout << "br :" << br.x << ' ' << br.y << "\n";
      for (int j = 1; j <= c; ++j) {
         Point cm = ::cm[j] - tr[i];
         if (ccw(bl, br)) {
            fail[j] |= (!(ccw(bl, cm) & ccw(cm, br)));
         } else {
            fail[j] |= (ccw(br, cm) & ccw(cm, bl));
         }
      }
   }
   int ans = 0;
   for (int i = 1; i <= c; ++i) ans += !fail[i];
   cout << ans << '\n';
   for (int i = 1; i <= c; ++i) if (!fail[i]) {
      cout << i << ' ';
   }
}

Subtask #1
30.0 / 30.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 4 ms 512 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 5 ms 512 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 640 KB Output is correct
4 Correct 89 ms 384 KB Output is correct
5 Correct 19 ms 384 KB Output is correct
6 Correct 379 ms 632 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 473 ms 520 KB Output is correct
2 Correct 456 ms 724 KB Output is correct
3 Correct 467 ms 768 KB Output is correct
4 Correct 374 ms 640 KB Output is correct