BOJ 2700 - 볼록 격자 다각형의 내부점

BOJ 2700 - 볼록 격자 다각형의 내부점

그냥 귀찮아서 볼록껍질로 풀었다. 그냥 열심히 외적을 써서 계산하면 되는 문제같다.

내부점 판정도 사실 필요없는데 템플릿에 있어서 썼다.

void solve() {
   int n;
   cin >> n;
   vector<pi> p(n);
   for (auto &[x, y]: p) cin >> x >> y;
   auto hull = graham(p);
   vector<pi> cand;
   int mn_y = 1e9, mx_y = -1e9, mn_x = 1e9, mx_x = -1e9;
   for (auto &[x, y]: hull) {
      mn_y = min(mn_y, y);
      mx_y = max(mx_y, y);
      mn_x = min(mn_x, x);
      mx_x = max(mx_x, x);
   }
   map<int, vi> yx;
   for (int y = mn_y; y <= mx_y; y++) {
      for (int x = mn_x; x <= mx_x; x++) {
         if (polygon_in_v(hull, {x, y})) {
            yx[y].pb(x);
            break;
         }
      }
      for (int x = mx_x; x >= mn_x; x--) {
         if (polygon_in_v(hull, {x, y})) {
            yx[y].pb(x);
            break;
         }
      }
   }
   for (auto &[y, xs]: yx) {
      sort(all(xs));
   }
   vector<array<int, 3>> ans;
   for (auto it = yx.rbegin(); it != yx.rend(); it++) {
      if (sz(it->se)) {
         ans.pb({it->fi, it->se[0], it->se.back()});
      }
   }
   cout << sz(ans) << endl;
   for (auto &[a, b, c]: ans) cout << a << ' ' << b << ' ' << c << endl;
}