Submission #117078

#	Time	Username	Problem	Language	Result	Execution time	Memory
117078		IOrtroiii	The Forest of Fangorn (CEOI14_fangorn)	C++14	50 / 100	398 ms	512 KiB

fangorn

#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 = 1010;
const int C = 10100;

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

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 / 30
• Subtask 2: 20 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 20