解法

editorialとほぼ同様。 実装の簡略化のため誤魔化しを入れたので計算量は曖昧。

メモ

• 記述時現在、私を含めてまだ4人しか通してないらしい。でもそこまでやばいやつではなかった
• PostScriptでvisualizerを書くのすごくよかった

実装

visualizer

#!/usr/bin/env python3
import math

# input
n = int(input())
xs, ys = [], []
for _ in range(n):
x, y = map(int, input().split())
xs += [ x ]
ys += [ y ]

# get the bounding box
lx, ly = 0, 0
rx, ry = 0, 0
for x, y in zip(xs, ys):
r = math.ceil(math.sqrt(x ** 2 + y ** 2))
lx = min(lx, x - r)
ly = min(ly, y - r)
rx = max(rx, x + r)
ry = max(ry, y + r)
lx -= 3
ly -= 3
rx += 3
ry += 3

scale = 30
dot = 3
print('%%BoundingBox:', *map(lambda z: int(z * scale), [ lx + 0.5, ly + 0.5, rx - 0.5, ry - 0.5]))

# background
print(1, 1, 1, 'setrgbcolor')  # white
print('newpath')
print(lx * scale, ly * scale, 'moveto')
print(lx * scale, ry * scale, 'lineto')
print(rx * scale, ry * scale, 'lineto')
print(rx * scale, ly * scale, 'lineto')
print(lx * scale, ly * scale, 'lineto')
print('fill')

# grid
print(0, 0, 0, 'setrgbcolor')  # black
for y in range(ly, ry + 1):
print('newpath')
print(lx * scale, y * scale, 'moveto')
print(rx * scale, y * scale, 'lineto')
print('stroke')

# grid
print(0, 0, 0, 'setrgbcolor')  # black
for x in range(lx, rx + 1):
print('newpath')
print(x * scale, ly * scale, 'moveto')
print(x * scale, ry * scale, 'lineto')
print('stroke')

# circles
print(0, 0, 1, 'setrgbcolor')  # blue
for x, y in zip(xs, ys):
r = math.sqrt(x ** 2 + y ** 2)
print('newpath')
print(x * scale, y * scale, r * scale, 0, 360, 'arc')  # circle
print('stroke')

# points
print(0, 0.8, 0, 'setrgbcolor')  # green
for y in range(ly, ry + 1):
for x in range(lx, rx + 1):
for x1, y1 in zip(xs, ys):
if (x - x1) ** 2 + (y - y1) ** 2 <= x1 ** 2 + y1 ** 2:
print('newpath')
print(x * scale, y * scale, dot, 0, 360, 'arc')  # circle
print('fill')
break

# origin
print(0.9, 0, 0, 'setrgbcolor')  # red
print('newpath')
print(0 * scale, 0 * scale, dot, 0, 360, 'arc')  # circle
print('fill')

# footer
print('%%EOF')


本体

#include <algorithm>
#include <cassert>
#include <cmath>
#include <iostream>
#include <tuple>
#include <vector>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define ALL(x) begin(x), end(x)
using ll = long long;
using namespace std;

ll sq(ll x) { return x * x; }

struct point_t { int y, x; };
ll dot(point_t a, point_t b) { return (ll)a.x * b.x + (ll)a.y * b.y; }
ll cross(point_t a, point_t b) { return (ll)a.x * b.y - (ll)a.y * b.x; }
ll sqabs(point_t a) { return dot(a, a); }
double abs(point_t a) { return sqrt(sqabs(a)); }

int ccw(point_t a, point_t b, point_t c) {
b.y -= a.y;
b.x -= a.x;
c.y -= a.y;
c.x -= a.x;
if (cross(b, c) > 0) return +1;  // counter clockwise
if (cross(b, c) < 0) return -1;  // clockwise
if (dot(b, c) < 0)   return +2;  // c--a--b on line
if (sqabs(b) < sqabs(c)) return -2;  // a--b--c on line
return 0;
}

vector<point_t> convex_hull(vector<point_t> ps) {
int n = ps.size();
if (n <= 2) return ps;
int k = 0;
sort(ps.begin(), ps.end(), [&](point_t const a, point_t const b) { return make_pair(a.x, a.y) < make_pair(b.x, b.y); });
vector<point_t> ch(2 * n);
for (int i = 0; i < n; ch[k ++] = ps[i ++]) {  // lower-hull
while (k >= 2 and ccw(ch[k - 2], ch[k - 1], ps[i]) <= 0) -- k;
}
for (int i = n - 2, t = k + 1; i >= 0; ch[k ++] = ps[i --]) {  // upper-hull
while (k >= t and ccw(ch[k - 2], ch[k - 1], ps[i]) <= 0) -- k;
}
ch.resize(k - 1);
return ch;
}

constexpr double eps = 1e-8;
constexpr int size = 300000;

pair<double, double> get_cross_points(point_t p, point_t q) {
// let ax + by + c = 0 be the line through p and q
ll a = q.y - p.y;
ll b = p.x - q.x;
ll c = - p.x * a - p.y * b;
assert (a * p.x + b * p.y + c == 0);
assert (a * q.x + b * q.y + c == 0);
assert (a != 0 or b != 0);
// bx - ay = 0 is the perpendicular
double x = - a * c / (pow(a, 2) + pow(b, 2));
double y = - b * c / (pow(a, 2) + pow(b, 2));
x *= 2;
y *= 2;
// assert (abs(pow(y - p.y, 2) + pow(x - p.x, 2) - (sq(p.y) + sq(p.x))) < eps);  // fails when eps is enough small to get AC
// assert (abs(pow(y - q.y, 2) + pow(x - q.x, 2) - (sq(q.y) + sq(q.x))) < eps);
return make_pair(y, x);
}

pair<int, int> get_xl_xr(point_t p, int y) {
// solve x^2 + bx + c = 0
int b = - 2 * p.x;
ll c = sq(p.x) + sq(y - p.y) - sqabs(p);
assert (sq(b) - 4 * c >= 0);
int x0 = - b / 2;
double dx = sqrt(sq(b) - 4 * c) / 2.0;
int xl = ceil(x0 - dx - eps);
int xr = ceil(x0 + dx + eps);
return make_pair(xl, xr);
}

pair<int, int> get_yl_yr(point_t p) {
double r = abs(p);
int yl = ceil(p.y - r - eps);
int yr = ceil(p.y + r + eps);
assert (- size <= yl and yl <= yr and yr <= size);
return make_pair(yl, yr);
}

int solve_for_y(int n, vector<point_t> const & ps, int y) {
int cnt = 0;
vector<pair<int, char> > imos;
for (auto p : ps) {
int yl, yr; tie(yl, yr) = get_yl_yr(p);
if (y < yl or yr <= y) continue;
int xl, xr; tie(xl, xr) = get_xl_xr(p, y);
imos.emplace_back(xl, +1);
imos.emplace_back(xr, -1);
}
sort(ALL(imos));
int last = - size;
int acc = 0;
for (auto it : imos) {
if (acc) cnt += it.first - last;
last = it.first;
acc += it.second;
}
return cnt;
}

ll solve(int n, vector<point_t> ps) {
ps = convex_hull(ps);
n = ps.size();

vector<tuple<int, int, int> > imos;
double last_y1 = INFINITY;
double last_x1 = INFINITY;
REP (i, n) {
point_t p = ps[i];

// points
int j1 = (i - 1 + n) % n;
int j2 = (i + 1) % n;
double y1, x1;
double y2, x2;
if (n <= 2) {
y1 = x1 = 0.0;
y2 = x2 = 0.0;
} else {
tie(y1, x1) = get_cross_points(p, ps[j1]);
tie(y2, x2) = get_cross_points(p, ps[j2]);
}

// angles
double a1 = atan2(y1 - p.y, x1 - p.x);
double a2 = atan2(y2 - p.y, x2 - p.x);
assert (- M_PI < a1 + eps and a1 < M_PI + eps);
assert (- M_PI < a2 + eps and a2 < M_PI + eps);

// some circles has the same point as (x1, y1)
if (abs(y1 - last_y1) < eps and abs(x1 - last_x1) < eps) {
a1 += eps;
}
last_y1 = y1;
last_x1 = x1;

bool plus_pi_2 =
(a1 < M_PI_2 + eps and M_PI_2 < a2 + eps)
or (a2 < a1 and a1 < M_PI_2 + eps)
or (M_PI_2 < a2 + eps and a2 < a1);
bool minus_pi_2 =
(a1 < - M_PI_2 + eps and - M_PI_2 < a2 + eps)
or (a2 < a1 and a1 < - M_PI_2 + eps)
or (- M_PI_2 < a2 + eps and a2 < a1);
bool start_right = (- M_PI_2 < a1 + eps and a1 <   M_PI_2 + eps);
bool start_left  = (  M_PI_2 < a1 + eps or  a1 < - M_PI_2 + eps);
bool end_right   = (- M_PI_2 < a2 + eps and a2 <   M_PI_2 + eps);
bool end_left    = (  M_PI_2 < a2 + eps or  a2 < - M_PI_2 + eps);

{ // the left half
vector<pair<int, int> > ranges;
if (n <= 2) {
int yl, yr; tie(yl, yr) = get_yl_yr(p);
ranges.emplace_back(yl, yr);
} else if (start_right and plus_pi_2 and minus_pi_2) {
int yl, yr; tie(yl, yr) = get_yl_yr(p);
ranges.emplace_back(yl, yr);
} else if (start_left and not minus_pi_2) {  // contained in it
int yl = ceil(y2 - eps);
int yr = ceil(y1 - eps);
ranges.emplace_back(yl, yr);
} else {
if (start_left and minus_pi_2) {  // starts in it and go to the right half
int yl = get_yl_yr(p).first;
int yr = ceil(y1 - eps);
ranges.emplace_back(yl, yr);
}
if (plus_pi_2 and end_left) {  // come from the right half and ends in it
int yl = ceil(y2 - eps);
int yr = get_yl_yr(p).second;
ranges.emplace_back(yl, yr);
}
}
for (auto range : ranges) {
int yl, yr; tie(yl, yr) = range;
REP3 (y, yl, yr) {
int xl = get_xl_xr(p, y).first;
imos.emplace_back(y, xl, +1);
}
}
}

{ // the right half
vector<pair<int, int> > ranges;
if (n <= 2) {
int yl, yr; tie(yl, yr) = get_yl_yr(p);
ranges.emplace_back(yl, yr);
} else if (start_left and minus_pi_2 and plus_pi_2) {  // use all of it
int yl, yr; tie(yl, yr) = get_yl_yr(p);
ranges.emplace_back(yl, yr);
} else if (start_right and not plus_pi_2) {  // containd in it
int yl = ceil(y1 - eps);
int yr = ceil(y2 - eps);
ranges.emplace_back(yl, yr);
} else {
if (start_right and plus_pi_2) {  // starts in it and go to the left half
int yl = ceil(y1 - eps);
int yr = get_yl_yr(p).second;
ranges.emplace_back(yl, yr);
}
if (minus_pi_2 and end_right) {  // come from the left half and ends in it
int yl = get_yl_yr(p).first;
int yr = ceil(y2 - eps);
ranges.emplace_back(yl, yr);
}
}
for (auto range : ranges) {
int yl, yr; tie(yl, yr) = range;
REP3 (y, yl, yr) {
int xr = get_xl_xr(p, y).second;
imos.emplace_back(y, xr, -1);
}
}
}

}

sort(ALL(imos));
imos.erase(unique(ALL(imos)), imos.end());
ll cnt = 0;
for (int i = 0; i < imos.size(); ) {
int y = get<0>(imos[i]);
int last = - size;
int acc = 0;
int cnt_y = 0;
for (; i < imos.size() and get<0>(imos[i]) == y; ++ i) {
if (acc < 0) continue;
int x, delta; tie(ignore, x, delta) = imos[i];
if (acc) cnt_y += x - last;
last = x;
acc += delta;
}
if (acc == 0) {
cnt += cnt_y;
} else {
cnt += solve_for_y(n, ps, y);
}
}
return cnt;
}

int main() {
int n; cin >> n;
vector<point_t> ps(n);
REP (i, n) {
int x, y; cin >> x >> y;
ps[i] = { y, x };
}
cout << solve(n, ps) << endl;
return 0;
}