Orientation and CCW

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
struct Pll { // Point with 64-bit integer coordinates
5
    long long x, y;
6
};
7
8
struct Pld { // Point with long double coordinates
9
    long double x, y;
10
};
11
12
// Sign function for long double with epsilon
13
int sgn(long double v, long double eps = 1e-12L) {
14
    if (fabsl(v) <= eps) return 0; // treat as zero (collinear)
15
    return v < 0 ? -1 : 1;
16
}
17
18
// Exact orientation for 64-bit integer coordinates using 128-bit intermediates
19
// Returns: +1 (CCW), -1 (CW), 0 (collinear)
20
int orient_exact(const Pll& a, const Pll& b, const Pll& c) {
21
    __int128 x1 = b.x - a.x;
22
    __int128 y1 = b.y - a.y;
23
    __int128 x2 = c.x - a.x;
24
    __int128 y2 = c.y - a.y;
25
    __int128 cross = x1 * y2 - y1 * x2; // exact for 64-bit inputs
26
    if (cross == 0) return 0;
27
    return cross > 0 ? +1 : -1;
28
}
29
30
// Floating-point orientation for real-valued coordinates with epsilon
31
int orient_fp(const Pld& a, const Pld& b, const Pld& c, long double eps = 1e-12L) {
32
    long double x1 = b.x - a.x;
33
    long double y1 = b.y - a.y;
34
    long double x2 = c.x - a.x;
35
    long double y2 = c.y - a.y;
36
    long double cross = x1 * y2 - y1 * x2;
37
    return sgn(cross, eps);
38
}
39
40
int main() {
41
    // Integer example
42
    Pll A{0, 0}, B{2, 0}, C{1, 1}, D{1, -1}, E{3, 0};
43
    cout << "orient_exact(A,B,C) = " << orient_exact(A,B,C) << " (CCW=+1)\n";
44
    cout << "orient_exact(A,B,D) = " << orient_exact(A,B,D) << " (CW=-1)\n";
45
    cout << "orient_exact(A,B,E) = " << orient_exact(A,B,E) << " (collinear=0)\n";
46
47
    // Floating-point example near collinear
48
    Pld a{0.0L, 0.0L}, b{1.0L, 1.0L}, c{2.0L, 2.0L + 1e-14L};
49
    cout << "orient_fp(a,b,c) with eps=1e-12 -> " << orient_fp(a,b,c,1e-12L) << "\n";
50
    cout << "orient_fp(a,b,c) with eps=1e-15 -> " << orient_fp(a,b,c,1e-15L) << "\n";
51
    return 0;
52
}
53

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
struct Pll { long long x, y; };
5
6
int orient_exact(const Pll& a, const Pll& b, const Pll& c) {
7
    __int128 x1 = b.x - a.x;
8
    __int128 y1 = b.y - a.y;
9
    __int128 x2 = c.x - a.x;
10
    __int128 y2 = c.y - a.y;
11
    __int128 cross = x1 * y2 - y1 * x2;
12
    if (cross == 0) return 0;
13
    return cross > 0 ? +1 : -1;
14
}
15
16
bool onSegment(const Pll& a, const Pll& b, const Pll& p) {
17
    // Assumes p, a, b are collinear; checks bounding box
18
    return min(a.x, b.x) <= p.x && p.x <= max(a.x, b.x) &&
19
           min(a.y, b.y) <= p.y && p.y <= max(a.y, b.y);
20
}
21
22
bool segmentsIntersect(const Pll& p1, const Pll& q1, const Pll& p2, const Pll& q2) {
23
    int o1 = orient_exact(p1, q1, p2);
24
    int o2 = orient_exact(p1, q1, q2);
25
    int o3 = orient_exact(p2, q2, p1);
26
    int o4 = orient_exact(p2, q2, q1);
27
28
    // General case: proper intersection
29
    if (o1 * o2 < 0 && o3 * o4 < 0) return true;
30
31
    // Collinear cases: check if endpoints lie on the other segment
32
    if (o1 == 0 && onSegment(p1, q1, p2)) return true;
33
    if (o2 == 0 && onSegment(p1, q1, q2)) return true;
34
    if (o3 == 0 && onSegment(p2, q2, p1)) return true;
35
    if (o4 == 0 && onSegment(p2, q2, q1)) return true;
36
37
    return false;
38
}
39
40
int main() {
41
    ios::sync_with_stdio(false);
42
    cin.tie(nullptr);
43
44
    // Example usage
45
    Pll a{0,0}, b{4,4};
46
    Pll c{0,4}, d{4,0};
47
    cout << (segmentsIntersect(a,b,c,d) ? "YES" : "NO") << "\n"; // YES (crossing)
48
49
    Pll e{1,1}, f{3,3};
50
    cout << (segmentsIntersect(a,b,e,f) ? "YES" : "NO") << "\n"; // YES (overlapping)
51
52
    Pll g{5,5}, h{7,7};
53
    cout << (segmentsIntersect(a,b,g,h) ? "YES" : "NO") << "\n"; // NO (disjoint collinear)
54
55
    return 0;
56
}
57

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
struct Pll { long long x, y; };
5
6
// Signed area * 2 using 128-bit to avoid overflow when summing
7
__int128 signed_area2(const vector<Pll>& poly) {
8
    int n = (int)poly.size();
9
    __int128 s = 0;
10
    for (int i = 0; i < n; ++i) {
11
        int j = (i + 1) % n;
12
        s += (__int128)poly[i].x * poly[j].y - (__int128)poly[i].y * poly[j].x;
13
    }
14
    return s; // equals 2 * signed area
15
}
16
17
// Ensure polygon is CCW; reverse if needed
18
void make_ccw(vector<Pll>& poly) {
19
    if (poly.size() < 3) return;
20
    if (signed_area2(poly) < 0) reverse(poly.begin(), poly.end());
21
}
22
23
int main() {
24
    vector<Pll> poly = {{0,0},{4,0},{4,3},{0,3}}; // rectangle, CW or CCW?
25
    __int128 A2 = signed_area2(poly);
26
    long double area = fabsl((long double)A2) / 2.0L;
27
    cout << fixed << setprecision(1);
28
    cout << "Area = " << area << "\n";
29
    cout << "Orientation = " << (A2 > 0 ? "CCW" : (A2 < 0 ? "CW" : "DEGENERATE")) << "\n";
30
31
    make_ccw(poly);
32
    cout << "After make_ccw: Orientation = " << (signed_area2(poly) > 0 ? "CCW" : "CW/DEG") << "\n";
33
    return 0;
34
}
35

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
struct Pll {
5
    long long x, y;
6
    bool operator<(const Pll& other) const {
7
        if (x != other.x) return x < other.x;
8
        return y < other.y;
9
    }
10
    bool operator==(const Pll& other) const {
11
        return x == other.x && y == other.y;
12
    }
13
};
14
15
int orient_exact(const Pll& a, const Pll& b, const Pll& c) {
16
    __int128 x1 = b.x - a.x;
17
    __int128 y1 = b.y - a.y;
18
    __int128 x2 = c.x - a.x;
19
    __int128 y2 = c.y - a.y;
20
    __int128 cross = x1 * y2 - y1 * x2;
21
    if (cross == 0) return 0;
22
    return cross > 0 ? +1 : -1;
23
}
24
25
vector<Pll> convex_hull(vector<Pll> pts, bool keep_collinear = false) {
26
    int n = (int)pts.size();
27
    sort(pts.begin(), pts.end());
28
    pts.erase(unique(pts.begin(), pts.end()), pts.end());
29
    if ((int)pts.size() <= 1) return pts;
30
31
    vector<Pll> lower, upper;
32
33
    // Build lower hull
34
    for (const auto& p : pts) {
35
        while (lower.size() >= 2) {
36
            int o = orient_exact(lower[lower.size()-2], lower[lower.size()-1], p);
37
            if (o > 0 || (keep_collinear && o == 0)) break; // keep left turns (and collinear if requested)
38
            lower.pop_back();
39
        }
40
        lower.push_back(p);
41
    }
42
43
    // Build upper hull
44
    for (int i = (int)pts.size()-1; i >= 0; --i) {
45
        const auto& p = pts[i];
46
        while (upper.size() >= 2) {
47
            int o = orient_exact(upper[upper.size()-2], upper[upper.size()-1], p);
48
            if (o > 0 || (keep_collinear && o == 0)) break;
49
            upper.pop_back();
50
        }
51
        upper.push_back(p);
52
    }
53
54
    // Concatenate lower and upper to form full hull; remove duplicate endpoints
55
    lower.pop_back();
56
    upper.pop_back();
57
    vector<Pll> hull = lower;
58
    hull.insert(hull.end(), upper.begin(), upper.end());
59
    return hull; // CCW order, starting from leftmost-lowest point
60
}
61
62
int main() {
63
    vector<Pll> pts = {{0,0},{1,1},{2,2},{0,2},{2,0},{1,0},{2,1}};
64
    auto hull = convex_hull(pts, /*keep_collinear=*/false);
65
    cout << "Hull size: " << hull.size() << "\n";
66
    for (auto& p : hull) cout << p.x << " " << p.y << "\n";
67
    return 0;
68
}
69