QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#564809#8858. Map Tilescrimson231AC ✓291ms5388kbC++2313.3kb2024-09-15 14:47:392024-09-15 14:47:40

Judging History

你现在查看的是最新测评结果

  • [2024-09-15 14:47:40]
  • 评测
  • 测评结果:AC
  • 用时:291ms
  • 内存:5388kb
  • [2024-09-15 14:47:39]
  • 提交

answer

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cassert>
#include <vector>
#include <queue>
typedef long long ll;
//typedef long double ld;
typedef double ld;
const ll INF = 1e17;
const int LEN = 20;
const ld TOL = 1e-7;
inline int sign(const ld& x) { return x < -TOL ? -1 : x > TOL; }
inline bool zero(const ld& x) { return !sign(x); }

#define __FUCK__ ;

int N, xs, ys;
int MAXX, MAXY, MINX, MINY;
short int board[LEN][LEN];
struct Pii {
	int x, y;
	inline Pii(int X = 0, int Y = 0) : x(X), y(Y) {}
	inline bool operator == (const Pii& p) const { return x == p.x && y == p.y; }
	inline bool operator < (const Pii& p) const { return x == p.x ? y < p.y : x < p.x; }
	inline Pii operator + (const Pii& p) const { return { x + p.x, y + p.y }; }
	inline Pii operator - (const Pii& p) const { return { x - p.x, y - p.y }; }
	inline Pii operator * (const int& n) const { return { x * n, y * n }; }
	inline Pii operator / (const int& n) const { return { x / n, y / n }; }
	inline ll operator * (const Pii& p) const { return (ll)x * p.x + (ll)y * p.y; }
	inline ll operator / (const Pii& p) const { return (ll)x * p.y - (ll)y * p.x; }
	inline Pii& operator += (const Pii& p) { x += p.x; y += p.y; return *this; }
	inline Pii& operator -= (const Pii& p) { x -= p.x; y -= p.y; return *this; }
	inline ll Euc() const { return (ll)x * x + (ll)y * y; }
	inline friend std::istream& operator >> (std::istream& is, Pii& p) { is >> p.x >> p.y; return is; }
	inline friend std::ostream& operator << (std::ostream& os, const Pii& p) { os << p.x << " " << p.y; return os; }
}; const Pii Oii = Pii(0, 0);
typedef std::vector<Pii> Polygon;
inline ll cross(const Pii& d1, const Pii& d2, const Pii& d3) { return (d2 - d1) / (d3 - d2); }
inline ll cross(const Pii& d1, const Pii& d2, const Pii& d3, const Pii& d4) { return (d2 - d1) / (d4 - d3); }
inline int ccw(const Pii& d1, const Pii& d2, const Pii& d3) { ll ret = cross(d1, d2, d3); return ret < 0 ? -1 : !!ret; }
inline ll area(const Polygon& H) {
	ll ret = 0;
	int sz = H.size();
	for (int i = 0; i < sz; i++) ret += H[i] / H[(i + 1) % sz];
	return ret;
}
inline void norm(Polygon& H) {
	ll A = area(H); assert(A);
	if (A < 0) std::reverse(H.begin(), H.end());
	auto s = std::min_element(H.begin(), H.end());
	std::rotate(H.begin(), s, H.end());
	return;
}
inline Polygon graham_scan(Polygon& C) {
	Polygon H;
	if (C.size() < 3) {
		std::sort(C.begin(), C.end());
		return C;
	}
	std::swap(C[0], *min_element(C.begin(), C.end()));
	std::sort(C.begin() + 1, C.end(), [&](const Pii& p, const Pii& q) -> bool {
		int ret = ccw(C[0], p, q);
		if (!ret) return (C[0] - p).Euc() < (C[0] - q).Euc();
		return ret > 0;
		}
	);
	C.erase(unique(C.begin(), C.end()), C.end());
	int sz = C.size();
	for (int i = 0; i < sz; i++) {
		while (H.size() >= 2 && ccw(H[H.size() - 2], H.back(), C[i]) <= 0)
			H.pop_back();
		H.push_back(C[i]);
	}
	return H;
}
inline bool inner_check(const Polygon& H, const Pii& p) {
	int sz = H.size();
	for (int i = 0; i < sz; i++) if (ccw(H[i], H[(i + 1) % sz], p) < 0) return 0;
	return 1;
}
inline int bfs(const int& x, const int& y, const int& val) {//flood fill
	Pii DRC[4] = { Pii(1, 0), Pii(0, 1), Pii(-1, 0), Pii(0, -1) };
	std::queue<Pii> Q;
	Q.push(Pii(x, y));
	board[y][x] = val;
	int cnt = 1;
	while (Q.size()) {
		Pii p = Q.front(); Q.pop();
		for (int i = 0; i < 4; i++) {
			Pii w = p + DRC[i];
			if ((MINX <= w.x) && (w.x <= MAXX) && (MINY <= w.y) && (w.y <= MAXY) && !board[w.y][w.x]) {
				Q.push(w);
				board[w.y][w.x] = val;
				cnt++;
			}
		}
	}
	return cnt;
}
struct Pos {
	ld x, y;
	inline Pos(ld X = 0, ld Y = 0) : x(X), y(Y) {}
	inline bool operator == (const Pos& p) const { return zero(x - p.x) && zero(y - p.y); }
	inline bool operator < (const Pos& p) const { return zero(x - p.x) ? y < p.y : x < p.x; }
	inline Pos operator + (const Pos& p) const { return { x + p.x, y + p.y }; }
	inline Pos operator - (const Pos& p) const { return { x - p.x, y - p.y }; }
	inline Pos operator * (const ld& scalar) const { return { x * scalar, y * scalar }; }
	inline Pos operator / (const ld& scalar) const { return { x / scalar, y / scalar }; }
	inline ld operator * (const Pos& p) const { return x * p.x + y * p.y; }
	inline ld operator / (const Pos& p) const { return x * p.y - y * p.x; }
	inline Pos& operator += (const Pos& p) { x += p.x; y += p.y; return *this; }
	inline Pos& operator -= (const Pos& p) { x -= p.x; y -= p.y; return *this; }
}; const Pos O = Pos(0, 0);
typedef std::vector<Pos> Polygonf;
inline ld cross(const Pos& d1, const Pos& d2, const Pos& d3) { return (d2 - d1) / (d3 - d2); }
inline ld dot(const Pos& d1, const Pos& d2, const Pos& d3) { return (d2 - d1) * (d3 - d2); }
inline int ccw(const Pos& d1, const Pos& d2, const Pos& d3) { ld ret = cross(d1, d2, d3); return sign(ret); }
inline bool on_seg_strong(const Pos& d1, const Pos& d2, const Pos& d3) { ld ret = dot(d1, d3, d2); return !ccw(d1, d2, d3) && sign(ret) >= 0; }
inline Pos intersection(const Pos& p1, const Pos& p2, const Pos& q1, const Pos& q2) { ld a1 = cross(q1, q2, p1), a2 = -cross(q1, q2, p2); return (p1 * a2 + p2 * a1) / (a1 + a2); }
inline bool inner_check(const Polygonf& H, const Pos& p) {//concave
	int sz = H.size(), cnt = 0;
	for (int i = 0; i < sz; i++) {
		Pos cur = H[i], nxt = H[(i + 1) % sz];
		if (on_seg_strong(cur, nxt, p)) return 1;
		if (cur.y == nxt.y) continue;
		if (nxt.y < cur.y) std::swap(cur, nxt);
		if (nxt.y - TOL < p.y || cur.y > p.y) continue;
		cnt += ccw(cur, nxt, p) > 0;
	}
	return cnt & 1;
}
inline Pos P(const Pii& p) { return Pos((ld)p.x, (ld)p.y); }
inline Pii P(const Pos& p) { return Pii(p.x + TOL, p.y + TOL); }
inline Pos cen(const int& i, const int& j, const int& xs, const int& ys) { return Pos(xs * (j + .5), ys * (i + .5)); }
inline Pos norm(Pos& p, const int& x, const int& y) {//fit in tile (0, 0), (xs, ys)
	while (sign(p.x) < 0) p.x += x;
	while (sign(p.x - x) >= 0) p.x -= x;
	while (sign(p.y) < 0) p.y += y;
	while (sign(p.y - y) >= 0) p.y -= y;
	return p;
}
inline void norm(int& x, const int& vx, const int& xs) {
	while (x <= (vx - xs)) x += xs;
	while (x > vx) x -= xs;
	return;
}
inline void norm(int& x, const ld& vx, const int& xs) {
	while (sign(x - (vx - xs)) <= 0) x += xs;
	while (sign(x - vx) > 0) x -= xs;
	return;
}
void sweep(const Pos& cur, const Pos& nxt, const int& xs, const int& ys) {//from 6632 arable
	int sx = 0, ex = 0, sy = 0, ey = 0;
	norm(sx, cur.x, xs);
	norm(ex, nxt.x, xs);
	norm(sy, cur.y, ys);
	norm(ey, nxt.y, ys);
	Pos d = nxt - cur;
	if (zero(d.x)) {
		if (sign(d.y) > 0) {
			if (zero(ey - nxt.y)) ey -= ys;
			if (zero(cur.x - sx) && zero(nxt.x - ex)) for (int i = sy; i <= ey; i += ys) board[i / ys][sx / xs - 1] = 1;
			else for (int i = sy; i <= ey; i += ys) board[i / ys][sx / xs] = 1;
		}
		else if (sign(d.y) < 0) {
			if (zero(sy - cur.y)) sy -= ys;
			for (int i = ey; i <= sy; i += xs) board[i / ys][sx / xs] = 1;
		}
		return;
	}
	if (zero(d.y)) {
		if (sign(d.x) > 0) {
			if (zero(ex - nxt.x)) ex -= xs;
			for (int i = sx; i <= ex; i += xs) board[sy / ys][i / xs] = 1;
		}
		else if (sign(d.x) < 0) {
			if (zero(sx - cur.x)) sx -= xs;
			if (zero(cur.y - sy) && zero(nxt.y - ey)) for (int i = ex; i <= sx; i += xs) board[sy / ys - 1][i / xs] = 1;
			else for (int i = ex; i <= sx; i += xs) board[sy / ys][i / xs] = 1;
		}
		return;
	}
	Pos s = cur, e = nxt;
	if (e < s) std::swap(s, e), std::swap(sx, ex), std::swap(sy, ey);
	int j = sx, i = sy;
	if (zero(e.x - ex)) ex -= xs;
	if (sign(std::abs(e.x - s.x) - std::abs(e.y - s.y)) >= 0) {
		if (s.y < e.y) {
			board[i / ys][j / xs] = 1;
			if (zero(e.y - ey)) ey -= ys;
			while (i <= ey) {
				while (j <= ex && ccw(s, e, Pos((ld)j, (ld)i + ys)) > 0 && ccw(s, e, Pos((ld)j + xs, (ld)i)) < 0) {
					board[i / ys][j / xs] = 1;
					j += xs;
				}
				if (ccw(s, e, Pos((ld)j - xs, (ld)i + 2. * ys)) > 0 && ccw(s, e, Pos(j, (ld)i + ys)) < 0) j -= xs;
				i += ys;
			}
		}
		else if (s.y > e.y) {
			board[i / ys - zero(s.y - sy)][j / xs] = 1;
			if (!zero(s.y - sy)) sy += ys, i += ys;
			while (i > ey) {
				while (j <= ex && ccw(s, e, Pos((ld)j + xs, (ld)i)) > 0 && ccw(s, e, Pos(j, (ld)i - ys)) < 0) {
					board[i / ys - 1][j / xs] = 1;
					j += xs;
				}
				if (ccw(s, e, Pos(j, (ld)i - ys)) > 0 && ccw(s, e, Pos((ld)j - xs, (ld)i - 2. * ys)) < 0) j -= xs;
				i -= ys;
			}
		}
	}
	else {
		if (s.y < e.y) {
			board[i / ys][j / xs] = 1;
			if (zero(e.y - ey)) ey -= ys;
			while (j <= ex) {
				while (i <= ey && ccw(s, e, Pos((ld)j, (ld)i + ys)) > 0 && ccw(s, e, Pos((ld)j + xs, (ld)i)) < 0) {
					board[i / ys][j / xs] = 1;
					i += ys;
				}
				if (ccw(s, e, Pos((ld)j + xs, (ld)i)) > 0 && ccw(s, e, Pos((ld)j + 2. * xs, (ld)i - ys)) < 0) i -= ys;
				j += xs;
			}
		}
		else if (s.y > e.y) {
			board[i / ys - zero(s.y - sy)][j / xs] = 1;
			if (!zero(s.y - sy)) sy += ys, i += ys;
			while (j <= ex) {
				while (i > ey && ccw(s, e, Pos((ld)j + xs, (ld)i)) > 0 && ccw(s, e, Pos((ld)j, (ld)i - ys)) < 0) {
					board[i / ys - 1][j / xs] = 1;
					i -= ys;
				}
				if (ccw(s, e, Pos((ld)j + 2. * xs, (ld)i + ys)) > 0 && ccw(s, e, Pos((ld)j + xs, (ld)i)) < 0) i += ys;
				j += xs;
			}
		}
	}
	return;
}
int sweep(const Polygonf& HF, const int& xs, const int& ys) {
	memset(board, 0, sizeof board);
	ld lx = 1e9, rx = -1e9, ly = 1e9, uy = -1e9;
	int sz = HF.size();
	for (int i = 0; i < sz; i++) {
		lx = std::min(lx, HF[i].x);
		rx = std::max(rx, HF[i].x);
		ly = std::min(ly, HF[i].y);
		uy = std::max(uy, HF[i].y);
		const Pos& cur = HF[i], & nxt = HF[(i + 1) % sz];
		sweep(cur, nxt, xs, ys);
	}
	MAXX = (int)rx / xs;
	MINX = (int)lx / xs;
	MAXY = (int)uy / ys;
	MINY = (int)ly / ys;
	MAXX += 2;
	MAXY += 2;
	for (int i = MINY; i <= MAXY; i++) {
		for (int j = MINX; j <= MAXX; j++) {
			if (!board[i][j]) {
				if (inner_check(HF, cen(i, j, xs, ys))) bfs(j, i, 1);
				else bfs(j, i, 2);
			}
		}
	}
	int cnt = 0;
	for (int i = MINY; i <= MAXY; i++) {
		for (int j = MINX; j <= MAXX; j++) {
			assert(board[i][j]);
			if (board[i][j] == 1) cnt++;
		}
	}
	return cnt;
}
void solve() {
	std::cin.tie(0)->sync_with_stdio(0);
	std::cout.tie(0);
	std::cout << std::fixed;
	std::cout.precision(7);
	std::cin >> N >> xs >> ys;
	Polygon H(N);
	Polygonf V;//All possible point
	for (int i = 0; i < N; i++) std::cin >> H[i];
	norm(H);
	Pii S = H[0];
	for (int i = 0; i < N; i++) {//O(50)
		for (int j = 0; j < N; j++) {//O(50 * 50)
			Pii I = H[i], J = H[j], K = H[(j + 1) % N];
			int x = I.x, y = J.y;
			Pos v = P(S - Pii(x, y));
			V.push_back(norm(v, xs, ys));
			if (J.x != K.x) {
				if (J.x > K.x) std::swap(J, K);
				int jx = I.x;
				norm(jx, J.x, xs);
				int kx = I.x;
				norm(kx, K.x, xs);
				Pii vec = K - J;
				for (int kw = jx; kw <= kx; kw += xs) {//O(50 * 50 * 20)
					if (kw < J.x || K.x < kw) continue;
					ld yh = J.y + ((ld)kw - J.x) * vec.y / vec.x;
					v = P(S) - Pos(I.x, yh);
					V.push_back(norm(v, xs, ys));
				}
			}

			I = H[i], J = H[j], K = H[(j + 1) % N];
			x = J.x, y = I.y;
			v = P(S - Pii(x, y));
			V.push_back(norm(v, xs, ys));
			if (J.y != K.y) {
				if (J.y > K.y) std::swap(J, K);
				int jy = I.y;
				norm(jy, J.y, ys);
				int ky = I.y;
				norm(ky, K.y, ys);
				Pii vec = K - J;
				for (int kh = jy; kh <= ky; kh += ys) {//O(50 * 50 * 20)
					if (kh < J.y || K.y < kh) continue;
					ld yw = J.x + ((ld)kh - J.y) * vec.x / vec.y;
					v = P(S) - Pos(yw, I.y);
					V.push_back(norm(v, xs, ys));
				}
			}
		}
	}
	std::sort(V.begin(), V.end());
	V.erase(unique(V.begin(), V.end()), V.end());
	for (int i = 0; i < N; i++) {//O(50)
		Pii I1 = H[i], I2 = H[(i + 1) % N];
		for (int j = 0; j < N; j++) {//O(50 * 50)
			Pii J1 = H[j], J2 = H[(j + 1) % N];
			if (i == j || !cross(I1, I2, J1, J2)) continue;
			Pii vec = I2 - I1;
			if (J2 < J1) std::swap(J1, J2);
			Polygon box = { J1, J1 - vec, J2, J2 - vec };
			box = graham_scan(box);
			assert(box.size() == 4);
			int lx = 1e9, rx = -1e9, ly = 1e9, uy = -1e9;
			for (int k = 0; k < 4; k++) {
				lx = std::min(lx, box[k].x);
				rx = std::max(rx, box[k].x);
				ly = std::min(ly, box[k].y);
				uy = std::max(uy, box[k].y);
			}
			int jx = I1.x;
			norm(jx, lx, xs);
			int jy = I1.y;
			norm(jy, ly, ys);
			for (int x = jx; x <= rx; x += xs) {//O(50 * 50 * 20)
				for (int y = jy; y <= uy; y += ys) {//O(50 * 50 * 20 * 20)
					if (inner_check(box, Pii(x, y))) {//O(50 * 50 * 20 * 20 * 4) == O(4000000)
						Pos o = intersection(P(J1), P(J2), Pos(x, y), Pos(x, y) + P(vec));
						Pos v = P(S) - o;
						V.push_back(norm(v, xs, ys));
					}
				}
			}
		}
	}
	std::sort(V.begin(), V.end());
	V.erase(unique(V.begin(), V.end()), V.end());
	Polygonf C(N);
	for (int i = 0; i < N; i++) C[i] = P(H[i]);
	int sz = V.size();
	int cnt = 1e6;
	for (int z = 0; z < sz; z++) {//O(50 * 50 * 20 * 20 * 4) == O(4000000)
		const Pos& s = V[z];
		Polygonf HF = C;
		Pos v = s - HF[0];
		ld miny = 1e9;
		for (int i = 0; i < N; i++) HF[i] += v, miny = std::min(miny, HF[i].y);
		int y = 0; norm(y, miny, ys);
		for (int i = 0; i < N; i++) HF[i].y -= y, HF[i] += Pos(xs, ys);
		cnt = std::min(cnt, sweep(HF, xs, ys));//O(50 * 50 * 20 * 20 * 4 * 50) == O(2,0000,0000)
	}
	std::cout << cnt << "\n";
	return;
}
int main() { solve(); return 0; }//boj8883

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3572kb

input:

12 9 9
1 8
1 16
6 16
9 29
19 31
23 24
30 23
29 18
20 12
22 8
14 0
14 8

output:

10

result:

ok single line: '10'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3660kb

input:

4 5 7
10 10
15 10
15 17
10 17

output:

1

result:

ok single line: '1'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3916kb

input:

12 9 9
2 17
2 25
7 25
10 38
20 40
24 33
31 32
30 27
21 21
23 17
15 9
15 17

output:

10

result:

ok single line: '10'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

4 5 7
11 12
16 12
16 19
11 19

output:

1

result:

ok single line: '1'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

12 4 3
0 0
0 12
8 12
8 9
4 9
4 3
8 3
8 6
12 6
12 12
16 12
16 0

output:

12

result:

ok single line: '12'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

12 4 3
0 0
0 12
8 12
8 9
4 9
4 4
8 3
8 6
12 6
12 12
16 12
16 0

output:

13

result:

ok single line: '13'

Test #7:

score: 0
Accepted
time: 3ms
memory: 3716kb

input:

12 5 6
2 2
50 3
49 5
4 41
16 39
6 46
9 55
49 23
46 16
50 9
49 59
3 60

output:

89

result:

ok single line: '89'

Test #8:

score: 0
Accepted
time: 3ms
memory: 3712kb

input:

12 6 5
2 2
3 50
5 49
41 4
39 16
46 6
55 9
23 49
16 46
9 50
59 49
60 3

output:

89

result:

ok single line: '89'

Test #9:

score: 0
Accepted
time: 50ms
memory: 3792kb

input:

46 98 79
468 612
408 594
421 658
439 616
469 744
9 464
113 776
314 771
169 735
481 768
513 709
780 506
799 751
702 715
596 788
818 760
832 595
967 753
948 511
875 545
975 385
964 47
924 139
886 5
489 8
478 23
302 5
319 78
608 140
510 274
694 386
641 219
700 241
708 193
898 267
884 500
493 490
383 34...

output:

80

result:

ok single line: '80'

Test #10:

score: 0
Accepted
time: 50ms
memory: 3832kb

input:

46 98 79
468 612
408 594
421 658
439 616
469 744
14 467
106 776
314 771
169 735
481 768
513 709
780 506
799 751
702 715
596 788
818 760
832 595
967 753
948 511
875 545
975 385
964 47
924 139
886 5
489 8
478 23
302 5
319 78
608 140
510 274
694 386
641 219
700 241
708 193
898 267
884 500
493 490
383 3...

output:

81

result:

ok single line: '81'

Test #11:

score: 0
Accepted
time: 48ms
memory: 3828kb

input:

46 79 98
612 468
594 408
658 421
616 439
744 469
464 9
776 113
771 314
735 169
768 481
709 513
506 780
751 799
715 702
788 596
760 818
595 832
753 967
511 948
545 875
385 975
47 964
139 924
5 886
8 489
23 478
5 302
78 319
140 608
274 510
386 694
219 641
241 700
193 708
267 898
500 884
490 493
345 38...

output:

80

result:

ok single line: '80'

Test #12:

score: 0
Accepted
time: 2ms
memory: 4008kb

input:

22 100 90
344 218
702 119
601 84
770 76
638 299
865 251
872 429
824 346
635 400
668 531
852 502
772 585
622 566
825 727
602 659
244 758
354 570
93 363
315 448
460 428
441 347
249 322

output:

45

result:

ok single line: '45'

Test #13:

score: 0
Accepted
time: 3ms
memory: 3708kb

input:

22 100 90
865 251
872 429
824 346
635 400
668 531
852 502
772 585
622 566
826 727
602 659
244 758
354 570
93 363
315 448
460 428
441 347
249 322
344 218
702 119
601 84
770 76
638 299

output:

46

result:

ok single line: '46'

Test #14:

score: 0
Accepted
time: 6ms
memory: 3764kb

input:

22 100 90
668 531
852 502
772 585
622 566
825 727
602 659
244 758
354 570
93 363
315 448
460 428
441 347
249 322
344 218
702 118
601 84
770 76
638 299
865 251
872 429
824 346
635 400

output:

46

result:

ok single line: '46'

Test #15:

score: 0
Accepted
time: 6ms
memory: 3812kb

input:

22 90 100
216 345
117 703
82 602
74 771
297 639
249 866
427 873
344 825
398 636
529 669
500 853
583 773
564 623
725 826
657 603
756 244
568 355
361 94
446 316
426 461
345 442
320 250

output:

45

result:

ok single line: '45'

Test #16:

score: 0
Accepted
time: 77ms
memory: 3800kb

input:

50 100 100
475 951
448 474
379 489
326 357
105 665
172 482
30 540
59 297
253 309
89 424
271 315
231 37
404 53
283 139
273 337
115 431
289 334
132 448
576 153
650 215
606 54
744 302
845 182
737 403
943 219
815 623
943 340
844 696
648 561
761 536
799 422
755 450
455 466
489 934
693 679
550 954
997 942...

output:

95

result:

ok single line: '95'

Test #17:

score: 0
Accepted
time: 74ms
memory: 3752kb

input:

50 100 100
289 334
132 449
576 153
650 215
606 54
744 302
845 182
737 403
943 219
815 623
943 340
844 696
648 561
761 536
799 422
755 450
455 466
489 934
693 679
550 954
997 942
960 406
997 277
908 374
995 165
791 336
995 104
732 218
996 15
542 5
618 156
507 14
25 4
23 940
475 951
448 474
379 489
32...

output:

96

result:

ok single line: '96'

Test #18:

score: 0
Accepted
time: 76ms
memory: 3848kb

input:

50 100 100
951 525
474 552
489 621
357 674
665 895
482 828
540 970
297 941
309 747
424 911
315 729
37 769
53 596
139 717
337 727
431 885
334 711
448 868
153 424
215 350
54 394
302 256
182 155
403 263
219 57
623 185
340 57
696 156
561 352
536 239
422 201
450 245
466 545
934 511
679 307
954 450
942 3
...

output:

95

result:

ok single line: '95'

Test #19:

score: 0
Accepted
time: 12ms
memory: 3732kb

input:

19 73 97
50 37
380 532
370 732
713 791
263 908
104 409
18 2
501 124
701 293
440 595
608 319
601 234
430 119
24 11
294 832
571 798
316 772
328 520
308 430

output:

54

result:

ok single line: '54'

Test #20:

score: 0
Accepted
time: 12ms
memory: 3728kb

input:

19 73 97
294 832
571 798
316 772
328 520
308 430
50 37
380 533
370 732
713 791
263 908
104 409
18 2
501 124
701 293
440 595
608 319
601 234
430 119
24 11

output:

54

result:

ok single line: '54'

Test #21:

score: 0
Accepted
time: 12ms
memory: 3740kb

input:

19 97 73
430 308
520 328
772 316
798 571
832 294
11 24
119 430
234 601
319 608
595 440
293 701
124 501
2 18
409 104
908 263
791 713
732 370
532 380
37 50

output:

54

result:

ok single line: '54'

Test #22:

score: 0
Accepted
time: 9ms
memory: 3728kb

input:

19 97 73
430 308
520 328
772 316
798 571
832 294
11 24
119 430
234 601
319 608
595 440
293 701
124 501
2 18
409 104
908 263
791 714
732 370
532 380
37 50

output:

55

result:

ok single line: '55'

Test #23:

score: 0
Accepted
time: 8ms
memory: 3988kb

input:

26 18 36
65 150
121 332
116 319
97 279
124 342
26 3
11 204
47 232
95 296
35 81
36 105
21 164
24 186
33 144
50 144
65 203
36 165
55 205
72 247
90 285
76 256
13 191
16 155
24 125
35 60
35 64

output:

31

result:

ok single line: '31'

Test #24:

score: 0
Accepted
time: 46ms
memory: 3780kb

input:

50 6 76
30 430
33 411
39 397
44 343
37 385
37 363
43 307
38 285
5 730
7 49
30 164
17 178
10 174
35 268
24 253
14 201
25 431
40 247
50 335
50 96
34 198
44 97
20 2
39 6
57 119
48 509
31 437
35 583
37 621
59 467
47 582
43 596
51 727
18 670
52 739
58 546
59 582
52 755
58 686
52 760
33 705
40 724
46 727
...

output:

83

result:

ok single line: '83'

Test #25:

score: 0
Accepted
time: 14ms
memory: 3804kb

input:

35 57 48
390 413
434 452
329 369
367 400
449 464
424 412
424 419
430 438
383 401
282 277
280 252
253 244
201 181
463 407
455 472
72 160
50 75
188 193
84 34
327 366
203 241
189 228
266 292
76 116
241 292
281 326
243 284
231 280
169 215
227 266
278 322
292 333
288 332
325 366
440 448

output:

25

result:

ok single line: '25'

Test #26:

score: 0
Accepted
time: 21ms
memory: 3768kb

input:

31 33 74
79 537
184 587
63 410
24 255
134 289
42 290
233 633
45 516
8 190
226 329
312 355
314 281
132 12
319 208
329 607
210 464
137 425
211 413
272 424
268 371
311 398
297 376
317 363
259 359
20 201
29 375
106 525
63 509
130 548
95 544
100 537

output:

56

result:

ok single line: '56'

Test #27:

score: 0
Accepted
time: 12ms
memory: 3724kb

input:

22 23 71
17 703
192 694
179 632
203 423
86 369
214 385
104 132
189 129
45 20
168 287
118 295
116 351
112 348
27 374
58 224
34 72
12 345
48 628
54 440
141 689
94 568
58 672

output:

68

result:

ok single line: '68'

Test #28:

score: 0
Accepted
time: 25ms
memory: 3736kb

input:

31 95 47
267 358
427 436
242 364
281 204
245 277
171 464
115 456
53 354
77 386
11 188
53 365
4 414
7 318
4 214
17 361
0 135
157 429
320 84
327 319
360 348
378 378
566 43
31 104
720 20
800 206
860 296
676 350
888 389
615 391
788 432
659 435

output:

71

result:

ok single line: '71'

Test #29:

score: 0
Accepted
time: 21ms
memory: 3800kb

input:

34 8 80
1 617
17 715
28 740
25 782
51 756
65 619
80 678
74 97
37 578
37 579
35 532
33 404
27 560
13 563
14 507
38 355
38 461
56 221
65 162
52 293
49 406
57 257
55 264
58 235
55 304
55 298
52 355
78 7
37 19
75 45
1 532
30 622
69 417
32 754

output:

71

result:

ok single line: '71'

Test #30:

score: 0
Accepted
time: 28ms
memory: 3728kb

input:

36 37 5
255 38
287 32
286 40
277 44
258 42
253 37
252 37
246 40
247 44
93 35
47 22
60 25
232 42
350 2
350 1
203 28
152 22
99 25
261 7
169 3
155 12
71 10
114 14
17 7
96 47
87 40
294 46
174 43
360 50
363 27
347 25
345 14
324 46
332 12
297 46
303 27

output:

77

result:

ok single line: '77'

Test #31:

score: 0
Accepted
time: 9ms
memory: 3732kb

input:

23 46 3
61 19
77 28
273 30
309 22
185 17
362 22
307 23
316 25
418 30
354 24
359 24
378 23
452 25
295 18
418 24
160 13
361 18
375 8
327 2
26 4
187 21
248 21
277 28

output:

70

result:

ok single line: '70'

Test #32:

score: 0
Accepted
time: 64ms
memory: 3732kb

input:

50 79 44
3 389
96 432
79 440
47 430
58 436
34 425
17 429
12 424
30 420
2 411
6 288
11 219
206 375
98 295
56 329
87 357
13 371
104 396
609 351
90 208
60 93
164 12
255 174
736 223
513 40
241 86
312 15
326 41
603 12
719 63
561 57
556 19
410 45
298 49
313 59
527 34
719 204
626 75
773 180
666 340
370 259...

output:

82

result:

ok single line: '82'

Test #33:

score: 0
Accepted
time: 0ms
memory: 3928kb

input:

4 100 100
0 0
0 1000
1000 1000
1000 0

output:

100

result:

ok single line: '100'

Test #34:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

3 1 1
5 5
5 6
6 6

output:

1

result:

ok single line: '1'

Test #35:

score: 0
Accepted
time: 1ms
memory: 3664kb

input:

15 10 10
39 53
20 51
37 54
30 70
39 63
50 91
0 91
0 0
91 0
91 91
51 91
40 63
50 65
47 60
50 50

output:

99

result:

ok single line: '99'

Test #36:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

3 100 100
666 666
666 667
667 667

output:

1

result:

ok single line: '1'

Test #37:

score: 0
Accepted
time: 28ms
memory: 3772kb

input:

50 100 100
0 0
999 1
0 2
999 3
0 4
999 5
0 6
999 7
0 8
999 9
0 10
999 11
0 12
999 13
0 14
999 15
0 16
999 17
0 18
999 19
0 20
999 21
0 22
999 23
0 24
999 25
0 26
999 27
0 28
999 29
0 30
999 31
0 32
999 33
0 34
999 35
0 36
999 37
0 38
999 39
0 40
999 41
0 42
999 43
0 44
999 45
0 46
999 47
1000 1000
1...

output:

19

result:

ok single line: '19'

Test #38:

score: 0
Accepted
time: 57ms
memory: 4024kb

input:

50 100 100
0 0
1 999
2 1
3 999
4 1
5 999
6 1
7 999
8 1
9 999
10 1
11 999
12 1
13 999
14 1
15 999
16 1
17 999
18 1
19 999
20 1
21 999
22 1
23 999
24 1
25 999
26 1
27 999
28 1
29 999
30 1
31 999
32 1
33 999
34 1
35 999
36 1
37 999
38 1
39 999
40 1
41 999
42 1
43 999
44 1
45 999
46 1
47 999
1000 1000
4...

output:

64

result:

ok single line: '64'

Test #39:

score: 0
Accepted
time: 0ms
memory: 3868kb

input:

3 1 100
4 4
8 4
6 10

output:

4

result:

ok single line: '4'

Test #40:

score: 0
Accepted
time: 0ms
memory: 3908kb

input:

3 100 1
4 4
8 4
6 10

output:

6

result:

ok single line: '6'

Test #41:

score: 0
Accepted
time: 1ms
memory: 3680kb

input:

12 9 9
8 1
16 1
16 6
29 9
31 19
24 23
23 30
18 29
12 20
8 22
0 14
8 14

output:

10

result:

ok single line: '10'

Test #42:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

4 5 7
10 10
15 10
15 17
10 17

output:

1

result:

ok single line: '1'

Test #43:

score: 0
Accepted
time: 0ms
memory: 3568kb

input:

11 40 60
169 157
219 157
219 197
259 217
209 317
169 317
169 287
149 247
129 247
129 217
169 217

output:

8

result:

ok single line: '8'

Test #44:

score: 0
Accepted
time: 0ms
memory: 3716kb

input:

16 4 6
15 11
12 11
11 12
11 17
4 17
4 12
3 11
0 11
0 6
3 6
4 5
4 0
11 0
11 5
12 6
15 6

output:

8

result:

ok single line: '8'

Test #45:

score: 0
Accepted
time: 1ms
memory: 3672kb

input:

20 100 100
1 1
451 1
451 0
452 0
452 1
901 1
901 451
902 451
902 452
901 452
901 901
452 901
452 902
451 902
451 901
1 901
1 452
0 452
0 451
1 451

output:

85

result:

ok single line: '85'

Test #46:

score: 0
Accepted
time: 0ms
memory: 3916kb

input:

4 1 1
5 0
10 5
5 10
0 5

output:

60

result:

ok single line: '60'

Test #47:

score: 0
Accepted
time: 1ms
memory: 3800kb

input:

28 5 5
7 41
7 13
46 13
46 41
13 41
13 17
40 17
40 37
19 37
19 21
34 21
34 33
25 33
25 25
28 25
28 31
31 31
31 23
22 23
22 35
37 35
37 19
16 19
16 39
43 39
43 15
10 15
10 41

output:

48

result:

ok single line: '48'

Test #48:

score: 0
Accepted
time: 1ms
memory: 3816kb

input:

10 1 1
1 1
10 1
10 0
0 0
0 10
10 10
10 2
9 2
9 9
1 9

output:

35

result:

ok single line: '35'

Test #49:

score: 0
Accepted
time: 1ms
memory: 3580kb

input:

4 10 10
1 0
100 1
99 100
0 99

output:

100

result:

ok single line: '100'

Test #50:

score: 0
Accepted
time: 7ms
memory: 4008kb

input:

23 100 100
303 352
294 345
292 295
347 296
352 307
358 295
409 295
406 346
403 349
409 353
408 415
356 417
348 407
344 415
296 415
8 988
982 979
983 25
12 16
8 968
292 399
290 383
294 358

output:

99

result:

ok single line: '99'

Test #51:

score: 0
Accepted
time: 0ms
memory: 3664kb

input:

10 100 100
150 450
350 249
551 450
350 651
157 457
7 990
993 989
994 13
9 15
7 968

output:

95

result:

ok single line: '95'

Test #52:

score: 0
Accepted
time: 291ms
memory: 5216kb

input:

50 100 50
980 491
979 9
961 482
958 12
938 479
933 15
926 477
905 6
906 474
885 7
884 474
865 8
863 472
847 9
841 473
830 7
819 472
811 8
800 471
791 8
780 474
777 9
765 473
761 10
11 11
752 22
15 23
749 34
16 37
748 49
15 52
746 64
16 68
748 83
15 86
744 100
13 105
742 115
15 123
745 126
16 135
744...

output:

83

result:

ok single line: '83'

Test #53:

score: 0
Accepted
time: 259ms
memory: 5280kb

input:

50 97 93
3 922
7 10
956 11
954 920
947 22
15 20
11 901
25 33
938 32
938 916
931 40
31 42
27 900
34 48
926 47
928 904
921 57
40 57
44 897
47 64
916 65
913 901
906 73
55 73
59 895
65 80
901 79
898 899
893 89
73 88
71 896
82 97
887 100
879 916
880 108
90 106
85 893
98 116
874 117
866 912
866 122
106 12...

output:

58

result:

ok single line: '58'

Test #54:

score: 0
Accepted
time: 259ms
memory: 5388kb

input:

50 97 93
11 912
8 11
958 11
959 920
34 908
26 32
937 35
937 891
54 880
48 59
918 60
920 868
71 852
64 79
899 81
903 844
87 827
78 98
882 101
888 823
103 801
96 118
863 121
867 795
124 773
117 137
840 143
850 777
847 132
108 125
114 782
876 806
870 110
87 108
98 811
897 835
890 88
73 86
80 841
913 85...

output:

100

result:

ok single line: '100'