1. 1
2. 2
3. 3
4. 4
5. 5
6. 6
7. 7
8. 8
9. 9
10. 10
11. 11
12. 12
13. 13
14. 14
15. 15
16. 16
17. 17
18. 18
19. 19
20. 20
21. 21
22. 22
23. 23
24. 24
25. 25
26. 26
27. 27
28. 28
29. 29
30. 30
31. 31
32. 32
33. 33
34. 34
35. 35
36. 36
37. 37
38. 38
39. 39
40. 40
41. 41
42. 42
43. 43
44. 44
45. 45
46. 46
47. 47
48. 48
49. 49
50. 50
51. 51
52. 52
53. 53
54. 54
55. 55
56. 56
57. 57
58. 58
59. 59
60. 60

struct point {
	ll x, y;
	point() { x = y = 0; }
	point(ll _x, ll _y) : x(_x), y(_y) {}
	bool operator < (point p) const { return (x == p.x && y < p.y) || x < p.x; }
	bool operator == (point p) const { return x == p.x && y == p.y; }
};

double dist(point& p1, point& p2) { return hypot(p1.x - p2.x, p1.y - p2.y); }

struct vec {
	ll x, y;
	vec(ll _x, ll _y) : x(_x), y(_y) {}
	vec(point a, point b) { x = b.x - a.x, y = b.y - a.y; }
};

ll dot(vec a, vec b) { return a.x * b.x + a.y * b.y; }

ll norm_sq(vec v) { return v.x * v.x + v.y * v.y; }

ll cross(vec a, vec b) { return a.x * b.y - a.y * b.x; }

double angle(point a, point o, point b) {
	vec oa(o, a), ob(o, b);
	return acos(dot(oa, ob) / sqrt(norm_sq(oa) * norm_sq(ob)));
}

bool ccw(point p, point q, point r) { return cross(vec(p, q), vec(p, r)) > 0; }

bool in_polygon(point pt, const vector<point> & P) {
	double sum = 0;
	for (int i = 0; i < P.size() - 1; i++) {
		if (pt == P[i]) return true;
		ccw(pt, P[i], P[i + 1]) ? sum += angle(P[i], pt, P[i + 1]) : sum -= angle(P[i], pt, P[i + 1]);
	}
	return fabs(sum) > acos(-1.0);
}

ll area(const vector<point> & P) {
	ll res = 0;
	for (int i = 0; i < (int)P.size() - 1; i++) res += (P[i].x * P[i + 1].y - P[i + 1].x * P[i].y);
	return res;
	// return res / 2.0;
}

vector<point> convex_hull(vector<point> & P) {
	int n = P.size(), k = 0;
	vector<point> H(2 * n);
	sort(P.begin(), P.end());
	for (int i = 0; i < n; i++) {
		while (k >= 2 && ccw(H[k - 2], H[k - 1], P[i]) <= 0) k--;
		H[k++] = P[i];
	}
	for (int i = n - 2, t = k + 1; i >= 0; i--) {
		while (k >= t && ccw(H[k - 2], H[k - 1], P[i]) <= 0) k--;
		H[k++] = P[i];
	}
	H.resize(k);
	return H;
}