These are the notes for Competitive Programming episode 81, the third geometry episode. The cross product from episodes 79 and 80 does two more jobs today, still with integers only. Saplings in the Field asks for the integer points strictly inside a polygon. The brute force tests every integer point of the bounding box and gets TLE. The shoelace formula adds signed cross products round the fence to get twice the area in O(n). A real bug: without abs() a clockwise field gives -66. A gcd per side counts the points on the fence, and Pick's theorem 2A = 2I + B − 2 gives the points inside. Crossing Roads asks whether two segments share a point. Sampling road 1 with doubles says NO on a real crossing. Four orientation tests do it exactly, but without the collinear checks a T-junction says NO. Finally, the crossing point of two lines, with one division at the very end. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.
The real-life hook
How does a land surveyor measure an odd-shaped plot? He drives one peg and stretches a rope from it to every corner, which cuts the plot into a fan of triangles. Each triangle's area comes from its two ropes: half the cross product (episode 79: the cross product of two arrows is the area of the parallelogram they span). Over a dent, a rope triangle sticks out of the plot, but its two ropes turn the other way, so its cross product is negative and it takes itself away. So the surveyor walks round the fence once, adding signed cross products. That is the shoelace formula.
Problem G1 · Saplings in the Field
(Written for this course.)
- A field is a polygon with n ≤ 10^5 corners, given in order round the fence.
- Corners are integer points, |x|, |y| ≤ 10^6. The fence never crosses itself (a simple polygon).
- A sapling stands at every integer point. Print how many saplings are strictly inside the field (saplings on the fence don't count).
- The field may be dented (not convex), and the corners may be given clockwise or counterclockwise.
5
0 0
6 0
6 4
3 7
0 4
Expected: 24. This is a house-shaped field: a 6 × 4 rectangle with a roof up to (3,7).
Attempt 1: test every integer point of the bounding box (TLE)
where(p, q) returns 1 if q is inside, 0 if it is on the fence, and -1 if it is outside. It uses ray casting: send a ray from q to the right and count how many sides it crosses. An odd count means inside. Then main tests every integer point of the bounding box.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct P {
ll x, y;
P operator-(const P& o) const { return {x - o.x, y - o.y}; }
};
ll cross(P a, P b) { return a.x * b.y - a.y * b.x; }
int where(const vector<P>& p, P q) { // 1 inside, 0 on the fence, -1 outside
int n = p.size(), in = 0;
for (int i = 0; i < n; i++) {
P a = p[i], b = p[(i + 1) % n];
ll c = cross(b - a, q - a);
if (c == 0 && min(a.x, b.x) <= q.x && q.x <= max(a.x, b.x) && min(a.y, b.y) <= q.y && q.y <= max(a.y, b.y)) return 0;
if ((a.y > q.y) != (b.y > q.y) && (b.y > a.y ? c > 0 : c < 0)) in ^= 1; // a ray to the right crosses ab
}
return in ? 1 : -1;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<P> p(n);
for (auto& v : p) cin >> v.x >> v.y;
ll lx = LLONG_MAX, hx = LLONG_MIN, ly = LLONG_MAX, hy = LLONG_MIN;
for (auto& v : p) lx = min(lx, v.x), hx = max(hx, v.x), ly = min(ly, v.y), hy = max(hy, v.y);
ll inside = 0;
for (ll x = lx; x <= hx; x++)
for (ll y = ly; y <= hy; y++) // every integer point of the box
if (where(p, {x, y}) == 1) inside++;
cout << inside << "\n";
}
24
Correct. Now a big curved field (BR_BIG): 50000 corners (20i, i²/2500), so the box is about 10^6 wide and 10^6 tall. Only main changes:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct P {
ll x, y;
P operator-(const P& o) const { return {x - o.x, y - o.y}; }
};
ll cross(P a, P b) { return a.x * b.y - a.y * b.x; }
int where(const vector<P>& p, P q) { // 1 inside, 0 on the fence, -1 outside
int n = p.size(), in = 0;
for (int i = 0; i < n; i++) {
P a = p[i], b = p[(i + 1) % n];
ll c = cross(b - a, q - a);
if (c == 0 && min(a.x, b.x) <= q.x && q.x <= max(a.x, b.x) && min(a.y, b.y) <= q.y && q.y <= max(a.y, b.y)) return 0;
if ((a.y > q.y) != (b.y > q.y) && (b.y > a.y ? c > 0 : c < 0)) in ^= 1; // a ray to the right crosses ab
}
return in ? 1 : -1;
}
int main() {
int n = 50000;
vector<P> p(n); // a big curved field, corners up to 10^6
for (int i = 0; i < n; i++) p[i] = {i * 20LL, (ll)i * i / 2500};
ll lx = LLONG_MAX, hx = LLONG_MIN, ly = LLONG_MAX, hy = LLONG_MIN;
for (auto& v : p) lx = min(lx, v.x), hx = max(hx, v.x), ly = min(ly, v.y), hy = max(hy, v.y);
ll inside = 0;
for (ll x = lx; x <= hx; x++)
for (ll y = ly; y <= hy; y++) // every integer point of the box
if (where(p, {x, y}) == 1) inside++;
cout << inside << "\n";
}
The box holds about 10^12 points and each test walks all 50000 sides. It runs far beyond any time limit: the SyntaxPilot compiler stops it with Time Limit Exceeded (locally it was still running when stopped after 10 seconds). O(W · H · n).
The shoelace formula
Put the surveyor's peg at the origin O. Side i of the fence, from p[i] to p[i+1], makes a triangle with O.
- Twice the signed area of triangle (O, p[i], p[i+1]) is
cross(p[i], p[i+1])=x_i · y_{i+1} − y_i · x_{i+1}, the two corners seen as arrows from O. - Add it for every side, wrapping round (
p[n] = p[0], hence(i + 1) % n). The parts of the triangles outside the field cancel out: 2A = |Σ cross(p[i], p[i+1])|. - Counterclockwise corners give a positive sum, clockwise corners a negative one, so take the absolute value.
- With integer corners, 2A is always an integer. Keep it doubled and you never touch a double.
It is O(n), exact, and works for any simple polygon, convex or dented. The name comes from writing the products out in two columns: they criss-cross like shoelaces.
The abs() bug: a clockwise field
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct P {
ll x, y;
P operator-(const P& o) const { return {x - o.x, y - o.y}; }
};
ll cross(P a, P b) { return a.x * b.y - a.y * b.x; }
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<P> p(n);
for (auto& v : p) cin >> v.x >> v.y;
ll a2 = 0; // twice the area
for (int i = 0; i < n; i++) a2 += cross(p[i], p[(i + 1) % n]);
cout << a2 << "\n";
}
On the sample (counterclockwise):
66
So the area is 33: the 6 × 4 rectangle is 24 and the roof triangle (base 6, height 3) adds 9. The same field given clockwise:
5
0 0
0 4
3 7
6 4
6 0
-66
A negative area. On a judge that is Wrong Answer on the first clockwise test. The sign only tells the direction; the size is right.
Boundary points: gcd per side
Call B the number of integer points on the fence and I the number strictly inside (the answer).
A side from (x1, y1) to (x2, y2) with steps dx = x2 − x1, dy = y2 − y1 passes an integer point every (dx/g, dy/g), where g = gcd(|dx|, |dy|). So it has g + 1 integer points including both ends. Counting one end per side (the other end is the next side's start), each side contributes exactly g, and
B = Σ gcd(|dx|, |dy|) over all the sides.
For example a side going 6 across and 3 up has gcd(6, 3) = 3: it passes (2,1), (4,2) and ends at (6,3). On the house field: bottom gcd(6,0) = 6, right side gcd(0,4) = 4, the two roof sides gcd(3,3) = 3 each, left side gcd(0,4) = 4. B = 20. (gcd(k, 0) = k, so horizontal and vertical sides work.)
Pick's theorem
For a simple polygon with integer corners:
A = I + B/2 − 1, so doubled, with integers only: 2A = 2I + B − 2, and
I = (2A − B + 2) / 2.
On the house field: (66 − 20 + 2) / 2 = 48 / 2 = 24, the same as the brute force. The division is always exact. Both sums come from the same walk round the fence: O(n) steps plus one gcd per side, O(n log C) with C = 10^6.
The fix: abs(), gcd and Pick in one loop
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct P {
ll x, y;
P operator-(const P& o) const { return {x - o.x, y - o.y}; }
};
ll cross(P a, P b) { return a.x * b.y - a.y * b.x; }
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<P> p(n);
for (auto& v : p) cin >> v.x >> v.y;
ll a2 = 0, b = 0;
for (int i = 0; i < n; i++) {
P u = p[i], v = p[(i + 1) % n];
a2 += cross(u, v); // shoelace: twice the signed area
b += gcd(abs(v.x - u.x), abs(v.y - u.y)); // integer points on this side
}
a2 = abs(a2); // clockwise gives a negative sum
cout << (a2 - b + 2) / 2 << "\n"; // Pick: 2A = 2I + B - 2
}
24
Clockwise (the input above):
24
Edge case: the smallest kind of field, a triangle with a diagonal side:
3
0 0
4 0
0 4
3
Only (1,1), (1,2) and (2,1) are strictly inside: 2A = 16, B = 4 + 4 + gcd(4,4) = 12, (16 − 12 + 2) / 2 = 3.
The big curved field (PICK_BIG):
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct P {
ll x, y;
P operator-(const P& o) const { return {x - o.x, y - o.y}; }
};
ll cross(P a, P b) { return a.x * b.y - a.y * b.x; }
int main() {
int n = 50000;
vector<P> p(n); // a big curved field, corners up to 10^6
for (int i = 0; i < n; i++) p[i] = {i * 20LL, (ll)i * i / 2500};
ll a2 = 0, b = 0;
for (int i = 0; i < n; i++) {
P u = p[i], v = p[(i + 1) % n];
a2 += cross(u, v); // shoelace: twice the signed area
b += gcd(abs(v.x - u.x), abs(v.y - u.y)); // integer points on this side
}
a2 = abs(a2); // clockwise gives a negative sum
cout << (a2 - b + 2) / 2 << "\n"; // Pick: 2A = 2I + B - 2
}
166657056801
About 1.67 · 10^11 saplings, in a few milliseconds. The answer is far beyond int: every sum here is long long.
Stress test
Random small convex fields (the monotone chain hull from episode 80, on points with coordinates 0 … 8), checked against the brute force that tests every point of the 9 × 9 grid:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct P {
ll x, y;
P operator-(const P& o) const { return {x - o.x, y - o.y}; }
};
ll cross(P a, P b) { return a.x * b.y - a.y * b.x; }
int where(const vector<P>& p, P q) { // 1 inside, 0 on the fence, -1 outside
int n = p.size(), in = 0;
for (int i = 0; i < n; i++) {
P a = p[i], b = p[(i + 1) % n];
ll c = cross(b - a, q - a);
if (c == 0 && min(a.x, b.x) <= q.x && q.x <= max(a.x, b.x) && min(a.y, b.y) <= q.y && q.y <= max(a.y, b.y)) return 0;
if ((a.y > q.y) != (b.y > q.y) && (b.y > a.y ? c > 0 : c < 0)) in ^= 1; // a ray to the right crosses ab
}
return in ? 1 : -1;
}
vector<P> hull(vector<P> p) { // episode 80: monotone chain
sort(p.begin(), p.end(), [](P a, P b) { return tie(a.x, a.y) < tie(b.x, b.y); });
int n = p.size(), k = 0;
vector<P> h(2 * n);
for (int i = 0; i < n; i++) {
while (k >= 2 && cross(h[k - 1] - h[k - 2], p[i] - h[k - 1]) <= 0) k--;
h[k++] = p[i];
}
for (int i = n - 2, t = k + 1; i >= 0; i--) {
while (k >= t && cross(h[k - 1] - h[k - 2], p[i] - h[k - 1]) <= 0) k--;
h[k++] = p[i];
}
h.resize(k - 1);
return h;
}
ll pick(const vector<P>& p) {
ll a2 = 0, b = 0;
int n = p.size();
for (int i = 0; i < n; i++) {
P u = p[i], v = p[(i + 1) % n];
a2 += cross(u, v);
b += gcd(abs(v.x - u.x), abs(v.y - u.y));
}
return (abs(a2) - b + 2) / 2;
}
int main() {
mt19937 gen(81);
int done = 0;
for (int it = 1; it <= 300; it++) {
vector<P> pts(gen() % 8 + 3);
for (auto& v : pts) v = {(ll)(gen() % 9), (ll)(gen() % 9)};
vector<P> f = hull(pts);
if (f.size() < 3) continue; // not a real field
ll slow = 0;
for (ll x = 0; x <= 8; x++)
for (ll y = 0; y <= 8; y++) slow += where(f, {x, y}) == 1;
if (slow != pick(f)) { cout << "mismatch on test " << it; return 0; }
done++;
}
cout << "all " << done << " fields passed";
}
all 298 fields passed
Two of the 300 random point sets were all on one line (the hull had fewer than 3 corners), so they were not real fields and were skipped.
Problem G2 · Crossing Roads
(Written for this course.)
- q ≤ 2·10^5 queries. Each gives two roads, each a segment between integer points:
ax ay bx by cx cy dx dy(road 1 is a–b, road 2 is c–d). - Print
YESif the two roads share at least one point, otherwiseNO. - Touching counts: one road may end on the other (a T-junction), or both may lie on one line and overlap.
- |x|, |y| ≤ 10^9.
- Note: the point where two roads cross is usually not an integer point.
5
0 0 6 3 1 4 4 -1
0 0 4 0 2 0 2 5
0 0 4 0 2 0 6 0
0 0 2 2 3 3 5 5
0 0 4 0 1 1 3 2
Expected: YES YES YES NO NO (one per line). The five queries are: a real crossing; a T-junction (road 2 starts at (2,0) on road 1); two roads on one line that overlap; two roads on one line with a gap; two roads that don't reach each other.
Attempt 1: walk along road 1 with doubles (Wrong Answer)
Walk along road 1 in 1000 steps; at each step check whether the point lies on road 2 (cross product near zero, inside road 2's bounding box).
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> q;
while (q--) {
double ax, ay, bx, by, cx, cy, dx, dy;
cin >> ax >> ay >> bx >> by >> cx >> cy >> dx >> dy;
bool meet = false;
for (int k = 0; k <= 1000; k++) { // walk along road 1 in 1000 steps
double x = ax + (bx - ax) * k / 1000, y = ay + (by - ay) * k / 1000;
double c = (dx - cx) * (y - cy) - (dy - cy) * (x - cx);
if (fabs(c) < 1e-9 && min(cx, dx) <= x && x <= max(cx, dx) && min(cy, dy) <= y && y <= max(cy, dy)) meet = true;
}
cout << (meet ? "YES\n" : "NO\n");
}
}
NO
YES
YES
NO
NO
The first pair of roads clearly crosses, but the answer is NO. They cross at x = 34/13 ≈ 2.6154. No step lands exactly there, so every check misses. More steps won't save it: the crossing can be any fraction, and a looser tolerance gives false YES answers. We need an exact test.
Four orientation tests
Episode 79's orientation test: the sign of cross(b − a, c − a) says whether c is on the left (+1), on the right (−1) or exactly on the line (0) of a → b.
d1, d2= which side of road ab are c and d?d3, d4= which side of road cd are a and b?- If
d1 · d2 < 0andd3 · d4 < 0, each road splits the other: a proper crossing. - A zero means a point lies exactly on the line of the other road (it is collinear with it). It is on the road itself only if it lies between the two ends:
onSeg(a, b, c)checks the bounding box of a and b. This covers T-junctions, overlaps, and roads of length zero.
Four cross products per query, all integers: O(1). With |x|, |y| ≤ 10^9, each difference is up to 2·10^9 and each cross product up to about 8·10^18, which fits in long long (max ≈ 9.22·10^18), just.
The T-junction bug: only the strict test
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct P {
ll x, y;
P operator-(const P& o) const { return {x - o.x, y - o.y}; }
};
ll cross(P a, P b) { return a.x * b.y - a.y * b.x; }
int sgn(ll v) { return (v > 0) - (v < 0); }
bool onSeg(P a, P b, P c) { // c is on line ab: is it between a and b?
return min(a.x, b.x) <= c.x && c.x <= max(a.x, b.x) && min(a.y, b.y) <= c.y && c.y <= max(a.y, b.y);
}
bool meet(P a, P b, P c, P d) {
int d1 = sgn(cross(b - a, c - a)), d2 = sgn(cross(b - a, d - a)); // c, d: which side of ab?
int d3 = sgn(cross(d - c, a - c)), d4 = sgn(cross(d - c, b - c)); // a, b: which side of cd?
if (d1 * d2 < 0 && d3 * d4 < 0) return true; // a proper crossing
return false;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> q;
while (q--) {
P a, b, c, d;
cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y >> d.x >> d.y;
cout << (meet(a, b, c, d) ? "YES\n" : "NO\n");
}
}
YES
NO
NO
NO
NO
The crossing is YES now. But query 2 is a T-junction: (2,0) is exactly on road 1, so d1 = 0 and 0 · d2 is not negative. The answer is NO: Wrong Answer. Query 3 (an overlap on one line) has all four signs zero and is missed too. A zero sign never passes a strict test.
The fix: check every zero sign with onSeg
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct P {
ll x, y;
P operator-(const P& o) const { return {x - o.x, y - o.y}; }
};
ll cross(P a, P b) { return a.x * b.y - a.y * b.x; }
int sgn(ll v) { return (v > 0) - (v < 0); }
bool onSeg(P a, P b, P c) { // c is on line ab: is it between a and b?
return min(a.x, b.x) <= c.x && c.x <= max(a.x, b.x) && min(a.y, b.y) <= c.y && c.y <= max(a.y, b.y);
}
bool meet(P a, P b, P c, P d) {
int d1 = sgn(cross(b - a, c - a)), d2 = sgn(cross(b - a, d - a)); // c, d: which side of ab?
int d3 = sgn(cross(d - c, a - c)), d4 = sgn(cross(d - c, b - c)); // a, b: which side of cd?
if (d1 * d2 < 0 && d3 * d4 < 0) return true; // a proper crossing
if (d1 == 0 && onSeg(a, b, c)) return true; // an end touches the other road
if (d2 == 0 && onSeg(a, b, d)) return true;
if (d3 == 0 && onSeg(c, d, a)) return true;
if (d4 == 0 && onSeg(c, d, b)) return true;
return false;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> q;
while (q--) {
P a, b, c, d;
cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y >> d.x >> d.y;
cout << (meet(a, b, c, d) ? "YES\n" : "NO\n");
}
}
YES
YES
YES
NO
NO
YES for the crossing, YES for the T-junction, YES for the overlap, NO for two collinear roads with a gap ((0,0)–(2,2) and (3,3)–(5,5): all signs zero, but no end lies between the other road's ends), and NO for two roads that don't reach each other.
Stress test
The exact slow way: walk along road 1 in 840 steps, but with every coordinate multiplied by 840, so the walk stays in integers. On a tiny 3 × 3 grid every possible crossing point has a denominator dividing 840, so it lands exactly on a step.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct P {
ll x, y;
P operator-(const P& o) const { return {x - o.x, y - o.y}; }
};
ll cross(P a, P b) { return a.x * b.y - a.y * b.x; }
int sgn(ll v) { return (v > 0) - (v < 0); }
bool onSeg(P a, P b, P c) { // c is on line ab: is it between a and b?
return min(a.x, b.x) <= c.x && c.x <= max(a.x, b.x) && min(a.y, b.y) <= c.y && c.y <= max(a.y, b.y);
}
bool meet(P a, P b, P c, P d) {
int d1 = sgn(cross(b - a, c - a)), d2 = sgn(cross(b - a, d - a)); // c, d: which side of ab?
int d3 = sgn(cross(d - c, a - c)), d4 = sgn(cross(d - c, b - c)); // a, b: which side of cd?
if (d1 * d2 < 0 && d3 * d4 < 0) return true; // a proper crossing
if (d1 == 0 && onSeg(a, b, c)) return true; // an end touches the other road
if (d2 == 0 && onSeg(a, b, d)) return true;
if (d3 == 0 && onSeg(c, d, a)) return true;
if (d4 == 0 && onSeg(c, d, b)) return true;
return false;
}
int main() {
mt19937 gen(81);
for (int it = 1; it <= 2000; it++) {
P s[4];
for (auto& v : s) v = {(ll)(gen() % 3), (ll)(gen() % 3)};
bool slow = false; // exact walk: 840 steps, scaled by 840
for (ll k = 0; k <= 840 && !slow; k++) {
P q = {s[0].x * 840 + (s[1].x - s[0].x) * k, s[0].y * 840 + (s[1].y - s[0].y) * k};
P c = {s[2].x * 840, s[2].y * 840}, d = {s[3].x * 840, s[3].y * 840};
if (cross(d - c, q - c) == 0 && onSeg(c, d, q)) slow = true;
}
if (slow != meet(s[0], s[1], s[2], s[3])) { cout << "mismatch on test " << it; return 0; }
}
cout << "all 2000 tests passed";
}
all 2000 tests passed
That includes roads of length zero (both ends the same point).
The crossing point of two lines
Sometimes the problem wants the point itself. Every point on line ab is a + t · (b − a). It is on line cd when cross(d − c, a + t(b − a) − c) = 0. Solving for t:
t = cross(c − a, d − c) / cross(b − a, d − c)
If the denominator den = cross(b − a, d − c) is 0, the directions are parallel: the lines are parallel (or the same line). Check that before dividing. Everything stays an exact integer until that one division at the end. (For segments, the point is on segment ab when 0 ≤ t ≤ 1.)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct P {
ll x, y;
P operator-(const P& o) const { return {x - o.x, y - o.y}; }
};
ll cross(P a, P b) { return a.x * b.y - a.y * b.x; }
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> q;
cout << fixed << setprecision(4);
while (q--) {
P a, b, c, d;
cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y >> d.x >> d.y;
ll den = cross(b - a, d - c);
if (den == 0) { cout << "PARALLEL\n"; continue; }
double t = (double)cross(c - a, d - c) / den; // how far along a -> b
cout << a.x + t * (b.x - a.x) << " " << a.y + t * (b.y - a.y) << "\n";
}
}
3
0 0 6 3 1 4 4 -1
0 0 4 0 2 0 2 5
0 0 2 2 1 0 3 2
2.6154 1.3077
2.0000 0.0000
PARALLEL
The first roads cross at (34/13, 17/13): no wonder the sampling missed it. The T-junction meets at (2,0). The third pair, (0,0)–(2,2) and (1,0)–(3,2), has the same direction: parallel.
Complexity vs the constraints
| Method | Time | Verdict |
|---|---|---|
| every point of the box × every side | O(W · H · n) ≈ 10^12 · n | TLE |
| sampling road 1 in 1000 steps | O(1000 q) | fast, but Wrong Answer |
| shoelace + gcd + Pick | O(n log C) | accepted, instant |
| four orientation tests | O(1) per query, O(q) total | accepted |
| crossing point of two lines | O(1) per query | accepted |
Memory: O(n) for the corners, O(1) per road query. Sizes: 2A up to about 8·10^12 for G1 and cross products up to about 8·10^18 for G2: long long everywhere.
Common mistakes (and the real outputs)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
no abs() on the shoelace sum |
-66 on the clockwise field |
clockwise input gives a negative sum | a2 = abs(a2) |
only the strict test d1 · d2 < 0 && d3 · d4 < 0 |
YES NO NO NO NO: the T-junction and the overlap say NO |
a zero sign is not negative | check every zero with onSeg |
| sampling points with doubles | NO on a real crossing |
the crossing is a fraction (34/13) | four orientation tests |
dividing before checking den |
inf inf for the parallel pair |
division by zero | if (den == 0) first |
int for the sums (int a2 = 0, b = 0; in PICK_BIG) |
846487745 instead of 166657056801 |
signed overflow (undefined behaviour) | long long |
(The inf inf and 846487745 lines were produced by removing the den == 0 line from the line-crossing program and by changing ll a2 = 0, b = 0; to int in PICK_BIG.)
Mini project
Field surveyor. Read a field, print twice its area, whether it is given clockwise, the number of saplings on the fence and inside, and its centroid. Then read roads one at a time and, for each road, print every side of the field it meets and the crossing point when it is a proper crossing.
Practice
These are the homework problems from the episode, plus one warm-up.
1. Is the field given clockwise? One sum: the sign of the shoelace sum (without abs).
Solution
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct P {
ll x, y;
P operator-(const P& o) const { return {x - o.x, y - o.y}; }
};
ll cross(P a, P b) { return a.x * b.y - a.y * b.x; }
int main() { // is the field given clockwise?
int n;
cin >> n;
vector<P> p(n);
for (auto& v : p) cin >> v.x >> v.y;
ll a2 = 0;
for (int i = 0; i < n; i++) a2 += cross(p[i], p[(i + 1) % n]); // signed: keep the sign
cout << (a2 > 0 ? "COUNTERCLOCKWISE" : "CLOCKWISE") << "\n";
}
On the sample and on its clockwise version:
COUNTERCLOCKWISE
CLOCKWISE
A simple polygon never has a zero sum, so the two cases are enough.
2. The centroid of a polygon. The balance point of a cardboard field. Split it into the triangles (O, p[i], p[i+1]): each has centroid (O + p[i] + p[i+1]) / 3 and signed weight cross(p[i], p[i+1]). Average them by weight.
Solution
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct P {
ll x, y;
P operator-(const P& o) const { return {x - o.x, y - o.y}; }
};
ll cross(P a, P b) { return a.x * b.y - a.y * b.x; }
int main() { // the centroid (balance point) of a polygon
int n;
cin >> n;
vector<P> p(n);
for (auto& v : p) cin >> v.x >> v.y;
ll a2 = 0, sx = 0, sy = 0;
for (int i = 0; i < n; i++) {
P u = p[i], v = p[(i + 1) % n];
ll c = cross(u, v); // twice the signed area of triangle (O, u, v)
a2 += c;
sx += (u.x + v.x) * c; // that triangle's centroid x, times 3, weighted
sy += (u.y + v.y) * c;
}
cout << fixed << setprecision(4) << (double)sx / (3.0 * a2) << " " << (double)sy / (3.0 * a2) << "\n";
}
House field:
3.0000 2.8182
Check: the rectangle (area 24, centroid y = 2) and the roof (area 9, centroid y = (4 + 4 + 7)/3 = 5) give y = (48 + 45) / 33 = 2.8182. The square (0,0) (4,0) (4,4) (0,4) gives 2.0000 2.0000. The signs of the weights and of a2 cancel, so clockwise input works too.
3. Does a closed path cross itself? (n ≤ 2000) Test every pair of sides with meet: O(n²) ≈ 2·10^6 pairs. Neighbouring sides always share a corner, so for them check only whether they fold back on one line.
Solution
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct P {
ll x, y;
P operator-(const P& o) const { return {x - o.x, y - o.y}; }
};
ll cross(P a, P b) { return a.x * b.y - a.y * b.x; }
int sgn(ll v) { return (v > 0) - (v < 0); }
bool onSeg(P a, P b, P c) { // c is on line ab: is it between a and b?
return min(a.x, b.x) <= c.x && c.x <= max(a.x, b.x) && min(a.y, b.y) <= c.y && c.y <= max(a.y, b.y);
}
bool meet(P a, P b, P c, P d) {
int d1 = sgn(cross(b - a, c - a)), d2 = sgn(cross(b - a, d - a));
int d3 = sgn(cross(d - c, a - c)), d4 = sgn(cross(d - c, b - c));
if (d1 * d2 < 0 && d3 * d4 < 0) return true;
if (d1 == 0 && onSeg(a, b, c)) return true;
if (d2 == 0 && onSeg(a, b, d)) return true;
if (d3 == 0 && onSeg(c, d, a)) return true;
if (d4 == 0 && onSeg(c, d, b)) return true;
return false;
}
ll dot(P a, P b) { return a.x * b.x + a.y * b.y; }
int main() { // does a closed path cross itself? O(n^2)
int n;
cin >> n;
vector<P> p(n);
for (auto& v : p) cin >> v.x >> v.y;
bool bad = false;
for (int i = 0; i < n && !bad; i++)
for (int j = i + 1; j < n && !bad; j++) {
P a = p[i], b = p[(i + 1) % n], c = p[j], d = p[(j + 1) % n];
if (j == i + 1 || (i == 0 && j == n - 1)) { // neighbours share one corner
P s = (j == i + 1) ? b : a; // the shared corner
P u = (j == i + 1) ? a : b, w = (j == i + 1) ? d : c; // the two far ends
if (cross(u - s, w - s) == 0 && dot(u - s, w - s) > 0) bad = true; // folds back on itself
} else if (meet(a, b, c, d)) bad = true;
}
cout << (bad ? "YES" : "NO") << "\n";
}
The bow tie (0,0) (2,2) (2,0) (0,2):
YES
The house field:
NO
The path (0,0) (4,0) (2,0) (2,3), whose second side runs back over the first:
YES
4. Cut a convex field with a straight line. Print the area left of the line a → b, then the area right of it. Walk the sides: keep the corners on the left, and add the crossing point (t = cu / (cu − cv) along the side) whenever a side changes sides. The right part is the total minus the left part.
Solution
Input: the field, then ax ay bx by on the last line.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct P {
ll x, y;
P operator-(const P& o) const { return {x - o.x, y - o.y}; }
};
ll cross(P a, P b) { return a.x * b.y - a.y * b.x; }
int main() { // cut a convex field by the line through a and b
int n;
cin >> n;
vector<P> p(n);
for (auto& v : p) cin >> v.x >> v.y;
P a, b;
cin >> a.x >> a.y >> b.x >> b.y;
vector<pair<double, double>> left; // the part on the left of a -> b
for (int i = 0; i < n; i++) {
P u = p[i], v = p[(i + 1) % n];
ll cu = cross(b - a, u - a), cv = cross(b - a, v - a);
if (cu >= 0) left.push_back({(double)u.x, (double)u.y});
if ((cu > 0 && cv < 0) || (cu < 0 && cv > 0)) { // the side crosses the line
double t = (double)cu / (cu - cv);
left.push_back({u.x + t * (v.x - u.x), u.y + t * (v.y - u.y)});
}
}
double l2 = 0, a2 = 0;
for (int i = 0; i < (int)left.size(); i++) {
auto [x1, y1] = left[i];
auto [x2, y2] = left[(i + 1) % left.size()];
l2 += x1 * y2 - y1 * x2;
}
for (int i = 0; i < n; i++) a2 += cross(p[i], p[(i + 1) % n]);
double L = fabs(l2) / 2, A = fabs((double)a2) / 2;
cout << fixed << setprecision(4) << L << " " << A - L << "\n";
}
The square (0,0) (4,0) (4,4) (0,4), line (0,0) → (4,2):
12.0000 4.0000
The house field, line (0,4) → (6,4) (cuts off the roof):
9.0000 24.0000
5. Saplings inside and on the fence. Print I, B and I + B (every sapling the field touches).
Solution
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct P {
ll x, y;
P operator-(const P& o) const { return {x - o.x, y - o.y}; }
};
ll cross(P a, P b) { return a.x * b.y - a.y * b.x; }
int main() { // saplings inside AND on the fence
int n;
cin >> n;
vector<P> p(n);
for (auto& v : p) cin >> v.x >> v.y;
ll a2 = 0, b = 0;
for (int i = 0; i < n; i++) {
P u = p[i], v = p[(i + 1) % n];
a2 += cross(u, v);
b += gcd(abs(v.x - u.x), abs(v.y - u.y));
}
a2 = abs(a2);
ll inside = (a2 - b + 2) / 2;
cout << inside << " " << b << " " << inside + b << "\n";
}
House field:
24 20 44
Quick quiz
// field corners, in order: (0,0) (8,0) (0,6)
// how many integer points are strictly inside?
A) 21 · B) 24 · C) 17 · D) 19
Answer
C) 17. 2A = 8 · 6 = 48. The fence has 8 + 6 + gcd(8, 6) = 8 + 6 + 2 = 16 points. I = (48 − 16 + 2) / 2 = 34 / 2 = 17. (The Pick program above prints 17 for this input.)
Interview questions
- How do you compute the area of a polygon from its corners? The shoelace formula: 2A = |Σ cross(p[i], p[i+1])|, O(n), exact for integer corners.
- Why does it work for a dented (non-convex) polygon? Each side forms a triangle with the origin; the triangles outside the polygon have the opposite sign and cancel out.
- What does the sign of the shoelace sum mean? Positive for counterclockwise order, negative for clockwise.
- How many integer points lie on a segment between integer points? gcd(|dx|, |dy|) + 1, including both ends.
- What is Pick's theorem? For a simple polygon with integer corners, A = I + B/2 − 1, so I = (2A − B + 2) / 2.
- How do you test whether two segments intersect? Four orientation tests: they properly cross if each segment's ends are on opposite sides of the other; for every zero sign, check that the point is between the other segment's ends.
- Why not use doubles or sampling? Crossing points are fractions; sampling skips them and tolerances give false answers. Integer cross products are exact.
- How do you find the intersection point of two lines? t = cross(c − a, d − c) / cross(b − a, d − c); a zero denominator means parallel.
- How do you test whether a point is inside a polygon? Ray casting: count the sides a ray to the right crosses; odd means inside (check the fence first).
Glossary
| Term | Meaning | Example |
|---|---|---|
| Polygon | A closed fence of straight sides through corners given in order | the house field |
| Simple polygon | A polygon whose fence never crosses itself | dents allowed, no bow ties |
| Convex / dented | No dents (every turn the same way) / at least one dent | episode 79 |
| Lattice (integer) point | A point with integer x and y | a sapling at (3,2) |
| Bounding box | The smallest axis-aligned rectangle around some points | x from 0 to 6, y from 0 to 7 |
| Vector (arrow) | A movement (dx, dy), b − a |
(6,3) |
| Cross product | a.x · b.y − a.y · b.x; twice the signed area of the triangle (O, a, b) |
cross((6,0),(6,4)) = 24 |
| Signed area | Area with a sign: + counterclockwise, − clockwise | −66 / 2 |
| Shoelace formula | 2A = |Σ cross(p[i], p[i+1])| | 66 for the house |
| Clockwise / counterclockwise | The order of the corners round the fence | the two sample inputs |
| gcd | Greatest common divisor; gcd(k, 0) = k | gcd(6, 3) = 3 |
| Boundary points B | Integer points on the fence: Σ gcd(|dx|, |dy|) | 20 |
| Interior points I | Integer points strictly inside | 24 |
| Pick's theorem | A = I + B/2 − 1, i.e. 2A = 2I + B − 2 | (66 − 20 + 2) / 2 = 24 |
| Ray casting | Inside test: count crossings of a ray to the right; odd = inside | where |
| Segment | The straight piece between two end points | a road a–b |
| Line | The infinite straight line through two points | line ab |
| Orientation | Left / right / on the line, from the sign of a cross product | sgn(cross(b − a, c − a)) |
| Collinear | Three or more points on one straight line | (0,0) (2,0) (4,0) |
| Proper crossing | Two segments crossing at one point inside both | query 1 |
| T-junction | One segment ends on the other | query 2 |
onSeg |
A collinear point is on the segment if it is in its bounding box | (2,0) on (0,0)–(4,0) |
| Parallel | Same direction: cross(b − a, d − c) = 0 |
PARALLEL |
| Parameter t | Position along a → b: a + t(b − a); 0 at a, 1 at b |
t = 17/39 |
| Centroid | The balance point of a shape | (3, 2.8182) |
| Stress test | A fast solution against a brute force on random inputs | all 2000 tests passed |
| TLE / WA | Time Limit Exceeded / Wrong Answer | brute force / sampling |
Summary
- Shoelace: 2A = |Σ cross(p[i], p[i+1])|, wrapping with
(i + 1) % n. The sign tells clockwise; takeabs. Keep the area doubled: exact integers. - Fence points: B = Σ gcd(|dx|, |dy|). Pick: 2A = 2I + B − 2, so I = (2A − B + 2) / 2. O(n log C),
long long. - Segments meet if each one splits the other (four signs), plus an
onSegcheck for every zero sign (T-junctions, overlaps, points). - Crossing point: t = cross(c − a, d − c) / cross(b − a, d − c), after checking
den == 0(parallel). One division, at the end.
Solutions in C++, Java and Python
Problem G1 · Saplings in the Field
C++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct P {
ll x, y;
P operator-(const P& o) const { return {x - o.x, y - o.y}; }
};
ll cross(P a, P b) { return a.x * b.y - a.y * b.x; }
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<P> p(n);
for (auto& v : p) cin >> v.x >> v.y;
ll a2 = 0, b = 0;
for (int i = 0; i < n; i++) {
P u = p[i], v = p[(i + 1) % n];
a2 += cross(u, v); // shoelace: twice the signed area
b += gcd(abs(v.x - u.x), abs(v.y - u.y)); // integer points on this side
}
a2 = abs(a2); // clockwise gives a negative sum
cout << (a2 - b + 2) / 2 << "\n"; // Pick: 2A = 2I + B - 2
}
Java
import java.util.*;
import java.io.*;
public class Main {
static long gcd(long a, long b) { return b == 0 ? a : gcd(b, a % b); }
public static void main(String[] args) throws IOException {
StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
st.nextToken();
int n = (int) st.nval;
long[] x = new long[n], y = new long[n];
for (int i = 0; i < n; i++) {
st.nextToken(); x[i] = (long) st.nval;
st.nextToken(); y[i] = (long) st.nval;
}
long a2 = 0, b = 0;
for (int i = 0; i < n; i++) {
int j = (i + 1) % n;
a2 += x[i] * y[j] - y[i] * x[j]; // shoelace: twice the signed area
b += gcd(Math.abs(x[j] - x[i]), Math.abs(y[j] - y[i])); // integer points on this side
}
a2 = Math.abs(a2); // clockwise gives a negative sum
System.out.println((a2 - b + 2) / 2); // Pick: 2A = 2I + B - 2
}
}
24
Python
import sys
from math import gcd
data = list(map(int, sys.stdin.buffer.read().split()))
n = data[0]
xs, ys = data[1:2 * n + 1:2], data[2:2 * n + 2:2]
a2 = b = 0
for i in range(n):
j = (i + 1) % n
a2 += xs[i] * ys[j] - ys[i] * xs[j] # shoelace: twice the signed area
b += gcd(abs(xs[j] - xs[i]), abs(ys[j] - ys[i])) # integer points on this side
a2 = abs(a2) # clockwise gives a negative sum
print((a2 - b + 2) // 2) # Pick: 2A = 2I + B - 2
24
All three print 24 on the sample, 24 on the clockwise version, 3 on the triangle, and 166657056801 on the big curved field.
Problem G2 · Crossing Roads
C++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct P {
ll x, y;
P operator-(const P& o) const { return {x - o.x, y - o.y}; }
};
ll cross(P a, P b) { return a.x * b.y - a.y * b.x; }
int sgn(ll v) { return (v > 0) - (v < 0); }
bool onSeg(P a, P b, P c) { // c is on line ab: is it between a and b?
return min(a.x, b.x) <= c.x && c.x <= max(a.x, b.x) && min(a.y, b.y) <= c.y && c.y <= max(a.y, b.y);
}
bool meet(P a, P b, P c, P d) {
int d1 = sgn(cross(b - a, c - a)), d2 = sgn(cross(b - a, d - a)); // c, d: which side of ab?
int d3 = sgn(cross(d - c, a - c)), d4 = sgn(cross(d - c, b - c)); // a, b: which side of cd?
if (d1 * d2 < 0 && d3 * d4 < 0) return true; // a proper crossing
if (d1 == 0 && onSeg(a, b, c)) return true; // an end touches the other road
if (d2 == 0 && onSeg(a, b, d)) return true;
if (d3 == 0 && onSeg(c, d, a)) return true;
if (d4 == 0 && onSeg(c, d, b)) return true;
return false;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> q;
while (q--) {
P a, b, c, d;
cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y >> d.x >> d.y;
cout << (meet(a, b, c, d) ? "YES\n" : "NO\n");
}
}
Java
import java.util.*;
import java.io.*;
public class Main {
static int sgn(long v) { return v > 0 ? 1 : (v < 0 ? -1 : 0); }
static long cross(long ax, long ay, long bx, long by, long cx, long cy) { // cross(b - a, c - a)
return (bx - ax) * (cy - ay) - (by - ay) * (cx - ax);
}
static boolean onSeg(long ax, long ay, long bx, long by, long cx, long cy) { // c on line ab: between a and b?
return Math.min(ax, bx) <= cx && cx <= Math.max(ax, bx) && Math.min(ay, by) <= cy && cy <= Math.max(ay, by);
}
static boolean meet(long[] s) {
long ax = s[0], ay = s[1], bx = s[2], by = s[3], cx = s[4], cy = s[5], dx = s[6], dy = s[7];
int d1 = sgn(cross(ax, ay, bx, by, cx, cy)), d2 = sgn(cross(ax, ay, bx, by, dx, dy)); // c, d: which side of ab?
int d3 = sgn(cross(cx, cy, dx, dy, ax, ay)), d4 = sgn(cross(cx, cy, dx, dy, bx, by)); // a, b: which side of cd?
if (d1 * d2 < 0 && d3 * d4 < 0) return true; // a proper crossing
if (d1 == 0 && onSeg(ax, ay, bx, by, cx, cy)) return true;
if (d2 == 0 && onSeg(ax, ay, bx, by, dx, dy)) return true;
if (d3 == 0 && onSeg(cx, cy, dx, dy, ax, ay)) return true;
if (d4 == 0 && onSeg(cx, cy, dx, dy, bx, by)) return true;
return false;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int q = Integer.parseInt(br.readLine().trim());
StringBuilder out = new StringBuilder();
long[] s = new long[8];
while (q-- > 0) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < 8; i++) s[i] = Long.parseLong(st.nextToken());
out.append(meet(s) ? "YES\n" : "NO\n");
}
System.out.print(out);
}
}
YES
YES
YES
NO
NO
Python
import sys
def cross(a, b, c): # cross(b - a, c - a)
return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])
def sgn(v):
return (v > 0) - (v < 0)
def on_seg(a, b, c): # c is on line ab: is it between a and b?
return min(a[0], b[0]) <= c[0] <= max(a[0], b[0]) and min(a[1], b[1]) <= c[1] <= max(a[1], b[1])
def meet(a, b, c, d):
d1, d2 = sgn(cross(a, b, c)), sgn(cross(a, b, d)) # c, d: which side of ab?
d3, d4 = sgn(cross(c, d, a)), sgn(cross(c, d, b)) # a, b: which side of cd?
if d1 * d2 < 0 and d3 * d4 < 0:
return True # a proper crossing
return ((d1 == 0 and on_seg(a, b, c)) or (d2 == 0 and on_seg(a, b, d)) or
(d3 == 0 and on_seg(c, d, a)) or (d4 == 0 and on_seg(c, d, b)))
data = list(map(int, sys.stdin.buffer.read().split()))
q = data[0]
out = []
for i in range(q):
v = data[1 + 8 * i: 9 + 8 * i]
a, b, c, d = (v[0], v[1]), (v[2], v[3]), (v[4], v[5]), (v[6], v[7])
out.append("YES" if meet(a, b, c, d) else "NO")
print("\n".join(out))
YES
YES
YES
NO
NO