[模板] 计算几何

#include <bits/stdc++.h>

#define debug(x) std::cerr << "[" << __LINE__ << "]: " << #x << " = " << x << "\n"

using i64 = long long;

#define UP 1
#define DOWN -1
#define COIN 0
typedef double db;
constexpr db eps = 1e-8;
namespace Geo {
    inline db min(db a, db b) { return a < b ? a : b; }
    inline db max(db a, db b) { return a > b ? a : b; }
    struct Point {
        db x, y;
        Point(db x = 0, db y = 0) : x(x), y(y) {}
        Point operator+(const Point &b) { return Point(x + b.x, y + b.y); }
        Point operator-(const Point &b) const { return Point(x - b.x, y - b.y); }
        Point operator/(db m) { assert(m != 0); return Point(x / m, y / m); }
        db operator*(const Point &b) { return (x * b.x) + (y * b.y); }
        db operator^(const Point &b) { return (x * b.y) - (y * b.x); }
        friend std::ostream& operator<<(std::ostream& os,const Point& p) {
            os << "(" << p.x << "," << p.y << ")"; return os; 
        }
    };
    typedef Point Vector;
    struct Line {
        Point a, b;
        Line(db x1, db y1, db x2, db y2) :a(x1, y1), b(x2, y2) {}
    };
    struct Polygon {
        std::vector<Point> poly;
        Polygon() {}
        void add_point(Point& p) { poly.emplace_back(p); }
        void add_point(db x, db y) { poly.emplace_back(x, y); }
        friend std::ostream& operator<<(std::ostream& os, const Polygon& obj) {
            for (int i = 0, sz = (int)obj.poly.size(); i < sz; i++) {
                os << obj.poly[i] << " ";
            }
            return os;
        }
        bool inside(const Point& p);
        db Circumstance();
        db Area();
    };
    inline db cross(Point& o, Point& a, Point& b) {
        return (a - o) ^ (b - o);
    }
    Point operator*(const Point& a, db m) { return Point(a.x * m, a.y * m); }
    Point operator*(db m, const Point& b) { return b * m; }
    
    inline db dist (Point& a, Point& b) { return std::sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));}
    inline int dcmp(db x) { return std::abs(x) < eps ? 0 : (x < 0 ? -1 : 1);}
    inline int side(Line& p, Point& q) {
        return dcmp(cross(p.a, q, p.b));
    }
    bool intersect(Line& l1, Line& l2) {
        if (max(l1.a.x, l1.b.x) < min(l2.a.x, l2.b.x)) return false;//排斥实验 
        if (max(l1.a.y, l1.b.y) < min(l2.a.y, l2.b.y)) return false;
        if (max(l2.a.x, l2.b.x) < min(l1.a.x, l1.b.x)) return false;
        if (max(l2.a.y, l2.b.y) < min(l1.a.y, l1.b.y)) return false;
        if (cross(l1.a, l2.a, l1.b) * cross(l1.a, l1.b, l2.b) < 0) return false;//跨立实验
        if (cross(l2.a, l1.a, l2.b) * cross(l2.a, l2.b, l1.b) < 0) return false;
        return true;
    }
    Point interpoint(Line& l1, Line& l2) {
        Vector v1 = Point(l1.b.x - l1.a.x, l1.b.y - l1.a.y);
        Vector v2 = Point(l2.b.x - l2.a.x, l2.b.y - l2.a.y);
        Vector u = l1.a - l2.a;
        db t = (v2 ^ u) / (v1 ^ v2);
        return Point(l1.a.x + v1.x * t, l1.a.y + v1.y * t);
    }
    bool onSegment(const Point& p1, const Point& p2,const Point& q) {
        return dcmp((p1 - q) ^ (p2 - q)) == 0 && dcmp((p1 - q) * (p2 - q)) <= 0;
    }
    bool onSegment(const Line& l,const Point& q) {
        return dcmp((l.a - q) ^ (l.b - q)) == 0 && dcmp((l.a - q) * (l.b - q)) <= 0;
    }
    bool Polygon::inside(const Point& p) {
        bool flag = false;
        for (int i = 0, sz = (int)poly.size(), j = sz - 1; i < sz; j = i++) {
            Point p1 = poly[i];
            Point p2 = poly[j];
            if (onSegment(p1, p2, p)) return true;
            if ((dcmp(p1.y - p.y) > 0) != (dcmp(p2.y - p.y) > 0) \
                && dcmp(p.x - (p.y - p1.y) * (p1.x - p2.x) / (p1.y - p2.y) - p1.x) < 0 )
            {
                flag = !flag;
            }
            return flag;
        }
    }
    db Polygon::Circumstance() {
        db ans = 0;
        for (int i = 0, sz = (int)poly.size(), j = sz - 1; i < sz; j = i++) {
            ans += dist(poly[i], poly[j]);
        }
        return ans;
    }
    db Polygon::Area(){
        db ans = 0;
        Point assist(0, 0);
        for (int i = 0, sz = (int)poly.size(), j = sz - 1; i < sz; j = i++) {
            ans += (poly[i] - assist) ^ (poly[j] - assist);
        }
        return std::abs(ans) * 0.5;
    }
};
using namespace Geo;
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout << std::fixed << std::setprecision(10);
    Polygon po;
    int n;
    std::cin >> n;
    for (int i = 0; i < n; i++) {
        double u, v;
        std::cin >> u >> v;
        po.add_point(u, v);

    }
    //std::cout << (po.inside(Point(0.9, 0.5)) ? "INSIDE" : "OUTSIDE") << "\n";
    //std::cout << po.Area();
    Line l1(0, 1, 2, 3), l2(2, 3, 4, 1);
    std::cout << intersect(l1, l2) << "\n";
    std::cout << interpoint(l1, l2) << "\n";
    return 0;
}