Hello!

Geometry problems often feel scary because they involve floating-point inaccuracies, trigonometric functions, and complex concepts like dot or cross products. This short blog shows you a clean way to avoid most of these challenges using simple integer arithmetic. Without any special templates or advanced math, you'll be able to tackle a wide range of geometric tasks easily and reliably.

Quick review on implemented functions:

• area2(A,B,C): Twice the area of triangle ABC. Equals 0 if A, B, C are collinear.
• area2(P): Twice the area of polygon P calculated by summing triangle areas.
• in(p, P): Checks if point p lies inside polygon P. Compares polygon area with the sum of triangles formed with p.
• dis2(A, B): Squared distance between points A and B, useful for length comparisons without the square root.
• dis(l,o): Distance between point o and line l. Uses integer area but returns real distance.
• isParallel(l1,l2): Checks if two lines l1 and l2 are parallel using three equal-area checks.
• isOnLine(l,p): Checks if point p lies exactly on line l.
• isOnLineFragment(x,y, a): Checks if point a lies on the line segment from x to y.

Implementation:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using Point = pair<int,int>;

struct Line{
    Point a,b;
    ll len2() const{
        ll dx = (ll)a.first - b.first;
        ll dy = (ll)a.second - b.second;
        return dx*dx + dy*dy;
    }
};

using Polygon = vector<Point>;

inline ll area2(const Point& A,const Point& B,const Point& C){
    return llabs((ll)A.first*B.second + (ll)B.first*C.second + (ll)C.first*A.second
               - (ll)A.second*B.first - (ll)B.second*C.first - (ll)C.second*A.first);
}

ll area2(const Polygon& P){
    if(P.size()<3) return 0;
    ll s=0;
    const Point& O=P[0];
    for(size_t i=1;i+1<P.size();++i) s+=area2(O,P[i],P[i+1]);
    return s;
}

bool in(const Point& p,const Polygon& P){
    ll sum=0,n=P.size();
    for(size_t i=0;i<n;++i)
        sum+=area2(p,P[i],P[(i+1)%n]);
    return sum==area2(P);
}

inline ll dis2(const Point& A,const Point& B){
    ll dx=(ll)A.first-B.first;
    ll dy=(ll)A.second-B.second;
    return dx*dx+dy*dy;
}

double dis(const Line& l,const Point& o){
    ll num=area2(o,l.a,l.b);
    return (double)num/std::sqrt((double)l.len2());
}

bool isParallel(const Line& l1,const Line& l2){
    ll a1=area2(l1.a,l2.a,l2.b);
    ll a2=area2(l1.b,l2.a,l2.b);
    Point c{2*l1.b.first - l1.a.first, 2*l1.b.second - l1.a.second}; // some other point on line l1
    ll a3=area2(c,l2.a,l2.b);
    return a1==a2 && a2==a3;
}

bool isOnLine(const Line& l,const Point& p){
    return area2(p,l.a,l.b)==0;
}

bool isOnLineFragment(const Point& x,const Point& y,const Point& a){
    if(!isOnLine(Line{x,y},a)) return false;
    return min(x.first,y.first)<=a.first && a.first<=max(x.first,y.first) &&
           min(x.second,y.second)<=a.second && a.second<=max(x.second,y.second);
}