计算几何

bool PointInPolygon(Point p, const Polygon & poly) {
    int n = poly.size();
    if (n < 3) return false;
    sort(poly.begin(), poly.end());
    Point b = poly[0], c = poly[1], a = poly[n - 1];
    bool clcws = ((b - a) ^ (c - b)) < 0;
    bool flag1 = true, flag2 = true;
    for (int i = 0; i < n; i++) {
        Line l(poly[i], poly[(i + 1) % n]);
        if (PointInSeg(p, l)) return true;
        int side = SideOfLine(p, l);
        if (clcws && side > 0) flag1 = false;
        if (!clcws && side < 0) flag2 = false;
        if (!flag1 && !flag2) return false;
    }
    return true;
}


Point LineCrossLine(Line l, Line m) {
    Point a = l.b - l.a, b = m.b - m.a, s = m.a - l.a;
    return l.a + a * ((b^s) / (b^a));
}

pair<int, Point> LineCrossSeg(Line l, Line seg) {
    int a = SideOfLine(seg.a, l);
    int b = SideOfLine(seg.b, l);
    if (a*b <= 0) return make_pair(1, LineCrossLine(l, seg));
    else return make_pair(0, Point(0, 0));
}

// polar angle order comparator
struct comp {
    Point p0;
    comp(const Point& p) :p0(p) {}
    bool operator ()(const Point& p1, const Point& p2) const {
        int s = epssgn((p1 - p0) ^ (p2 - p0));
        if (s == 0) return dist(p0, p1) < dist(p0, p2);
        else return s > 0;
    }
};

// polar angle order
int graham(vector<Point>& ps, vector<Point>& stk) {
    if (ps.size() < 3) return 0;
    stk.clear();
    sort(ps.begin(), ps.end());
    sort(ps.begin() + 1, ps.end(), comp(ps[0]));
    stk.push_back(ps[0]);
    stk.push_back(ps[1]);
    stk.push_back(ps[2]);
    for (int i = 3; i < ps.size(); i++) {
        while (true) {
            Point p2 = *(stk.end() - 1);
            Point p1 = *(stk.end() - 2);
            if (epssgn((p2 - p1) ^ (ps[i] - p2)) <= 0) stk.pop_back();
            else break;
        }
        stk.push_back(ps[i]);
    }
    return stk.size();
}

Grandpa's Estate

#include <iostream>
#include <vector>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <cstring>

using namespace std;

const double inf = 1e9;
const double eps = 1e-6;

struct Point {
    double x, y;
    Point(double a = 0, double b = 0) { x = a; y = b; }
    bool operator == (const Point& b) const {
        return x == b.x && y == b.y;
    }
    bool operator < (const Point& b) const {
        if (x == b.x) return y < b.y;
        return x < b.x;
    }
    friend ostream& operator << (ostream& os, const Point& p) {
        os << "(" << p.x << ", " << p.y << ")";
        return os;
    }
};

typedef Point Vector;

Vector operator + (Point a, Point b) { return Vector(a.x + b.x, a.y + b.y); }
Vector operator - (Point a, Point b) { return Vector(a.x - b.x, a.y - b.y); }
Vector operator * (Point a, double k) { return Vector(a.x*k, a.y*k); }
Vector operator * (double k, Point a) { return Vector(a.x*k, a.y*k); }
Vector operator / (Point a, double k) { return Vector(a.x / k, a.y / k); }
double operator * (Vector a, Vector b) { return a.x*b.x + a.y*b.y; }
double operator ^ (Vector a, Vector b) { return a.x*b.y - b.x*a.y; }
double len(Vector a) { return sqrt(a.x*a.x + a.y*a.y); }
Vector unit(Vector p) { return p * (1 / len(p)); }
double project(Vector a, Vector b) { return a * unit(b);}

struct Line {
    Point a, b;
    Line() {}
    Line(Point a, Point b) :a(a), b(b) {}
    double getx(double y) { return (y - a.y) / (b.y - a.y)*(b.x - a.x) + a.x; }
    double gety(double x) { return (x - a.x) / (b.x - a.x)*(b.y - a.y) + a.y; }
    friend ostream& operator <<(ostream& os, const Line & l){
        os << l.a << "->" << l.b;
        return os;
    }
};

int epssgn(double x) {
    if (fabs(x) < eps) return 0;
    else return x < 0 ? -1 : 1;
}

double dist(Point x, Point y) { return len(x - y); }
double dist(Point p, Line l) { return fabs((p - l.a) ^ (l.b - l.a)) / len(l.b - l.a);}
double area(Vector a, Vector b) { return a ^ b / 2;}

int SideOfLine(Point p, Point a, Point b) {
    double res = (b - a) ^ (p - a);
    if (epssgn(res) == 0) return 0;
    else if (res > 0) return 1;
    else return -1;
}

int SideOfLine(Point p, Line l) {
    return SideOfLine(p, l.a, l.b);
}

bool PointInSeg(Point p, Line l) {
    double tmp = (l.a - p) ^ (l.a - l.b);
    if (!epssgn(tmp) == 0) return false;
    if (epssgn(min(l.a.x, l.b.x) - p.x) <= 0 &&
        epssgn(p.x - max(l.a.x, l.b.x)) <= 0 &&
        epssgn(min(l.a.y, l.b.y) - p.y) <= 0 &&
        epssgn(p.y - max(l.a.y, l.b.y)) <= 0)
        return true;
    return false;
}

pair<int, Point> SegCrossSeg(Line s1, Line s2) {
    Point p1 = s1.a;
    Point p2 = s1.b;
    Point p3 = s2.a;
    Point p4 = s2.b;
    double a1 = area(p3 - p1, p4 - p1);
    double a2 = area(p4 - p2, p3 - p2);
    Point crossPoint = p1 + (p2 - p1)*(a1 / (a1 + a2));
    if (epssgn(((p2 - p1) ^ (p3 - p1))*((p2 - p1) ^ (p4 - p1))) < 0 &&
        epssgn(((p4 - p3) ^ (p1 - p3))*((p4 - p3) ^ (p2 - p3))) < 0)
        return make_pair(0, crossPoint); // standard cross
    if (epssgn((p2 - p1) ^ (p3 - p4)) != 0) {
        // 端点重合，不平行，不共线
        if (p1 == p3 || p1 == p4) return make_pair(1, p1);
        if (p2 == p3 || p2 == p4) return make_pair(1, p2);
        // s1端点在s2内部，不平行，不共线
        if (PointInSeg(p1, s2)) return make_pair(2, p1);
        if (PointInSeg(p2, s2)) return make_pair(2, p2);
        // s2端点在s1内部，不平行，不共线
        if (PointInSeg(p3, s1)) return make_pair(3, p3);
        if (PointInSeg(p4, s1)) return make_pair(3, p4);
        // s2所在直线与线段s1相交
        if (PointInSeg(crossPoint, s1)) return make_pair(8, crossPoint);
        // s1所在直线与线段s2相交
        if (PointInSeg(crossPoint, s2)) return make_pair(9, crossPoint);
        // 两直线相交
        return make_pair(4, crossPoint);
    }
    // 平行
    if (!epssgn(dist(p1, s2))) return make_pair(5, Point(0, 0)); 
    // 共线，有公共交点
    if (PointInSeg(p1, s2)) return make_pair(6, p1);
    if (PointInSeg(p2, s2)) return make_pair(6, p2);
    if (PointInSeg(p3, s1)) return make_pair(6, p3);
    if (PointInSeg(p4, s1)) return make_pair(6, p4);
    // 共线，无公共交点
    return make_pair(7, Point(0, 0));
}

// horizontal order graham
int graham(vector<Point>& ps, vector<Point>& stk) {
    int n = ps.size();
    if (n < 3) return 0;
    stk.clear();
    sort(ps.begin(), ps.end());
    stk.push_back(ps[0]);
    stk.push_back(ps[1]);
    for (int i = 2; i < n; i++) {
        while (stk.size() > 1) {
            Point p2 = *(stk.end() - 1);
            Point p1 = *(stk.end() - 2);
            if (epssgn((p2 - p1) ^ (ps[i] - p2)) < 0) stk.pop_back();
            else break;
        }
        stk.push_back(ps[i]);
    }
    int size = stk.size();
    stk.push_back(ps[n - 2]);
    for (int i = n - 3; i >= 0; i--) {
        while (stk.size() > size) {
            Point p2 = *(stk.end() - 1);
            Point p1 = *(stk.end() - 2);
            if (epssgn((p2 - p1) ^ (ps[i] - p2)) < 0) stk.pop_back();
            else break;
        }
        stk.push_back(ps[i]);
    }
    stk.pop_back();
    return stk.size();
}

const int maxn = 1005;
vector<Point> ps, hull;
int T, N, x, y;

int main() {
    cin >> T;
    while (T--) {
        cin >> N;
        ps.clear();
        for (int i = 0; i < N; i++) {
            cin >> x >> y;
            ps.push_back(Point(x, y));
        }
        if (N < 6) {
            cout << "NO" << endl;
            continue;
        }
        int s = graham(ps, hull);
        bool flag = true;
        for (int i = 0; i < s - 1; i++) {
            Line l(hull[i], hull[i + 1]);
            int cnt = 0;
            for (int j = 0; j < N; j++) if (SideOfLine(ps[j], l) == 0) cnt++;
            if (cnt < 3) {
                flag = false;
                break;
            }
        }
        if (flag) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}

Most Distant Point from the Sea

#include <iostream>
#include <vector>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <cstring>

using namespace std;

const double inf = 1e9;
const double eps = 1e-6;

struct Point {
    double x, y;
    Point(double a = 0, double b = 0) { x = a; y = b; }
    bool operator == (const Point& b) const {
        return x == b.x && y == b.y;
    }
    bool operator < (const Point& b) const {
        if (x == b.x) return y < b.y;
        return x < b.x;
    }
    friend ostream& operator << (ostream& os, const Point& p) {
        os << "(" << p.x << ", " << p.y << ")";
        return os;
    }
};

typedef Point Vector;

Vector operator + (Point a, Point b) { return Vector(a.x + b.x, a.y + b.y); }
Vector operator - (Point a, Point b) { return Vector(a.x - b.x, a.y - b.y); }
Vector operator * (Point a, double k) { return Vector(a.x*k, a.y*k); }
Vector operator * (double k, Point a) { return Vector(a.x*k, a.y*k); }
Vector operator / (Point a, double k) { return Vector(a.x / k, a.y / k); }
double len(Vector a) { return sqrt(a.x*a.x + a.y*a.y); }
Vector unit(Vector p) { return p * (1 / len(p)); }
double project(Vector a, Vector b) { return a * unit(b);}
double operator * (Vector a, Vector b) { return a.x*b.x + a.y*b.y; }
double operator ^ (Vector a, Vector b) { return a.x*b.y - b.x*a.y; }

struct Line {
    Point a, b;
    Line() {}
    Line(Point a, Point b) :a(a), b(b) {}
    double getx(double y) { return (y - a.y) / (b.y - a.y)*(b.x - a.x) + a.x; }
    double gety(double x) { return (x - a.x) / (b.x - a.x)*(b.y - a.y) + a.y; }
    friend ostream& operator <<(ostream& os, const Line & l){
        os << l.a << "->" << l.b;
        return os;
    }
};

int epssgn(double x) {
    if (fabs(x) < eps) return 0;
    else return x < 0 ? -1 : 1;
}

double dist(Point x, Point y) { return len(x - y); }
double dist(Point p, Line l) { return fabs((p - l.a) ^ (l.b - l.a)) / len(l.b - l.a);}
double area(Vector a, Vector b) { return a ^ b / 2;}

int SideOfLine(Point p, Point a, Point b) {
    double res = (b - a) ^ (p - a);
    if (epssgn(res) == 0) return 0;
    else if (res > 0) return 1;
    else return -1;
}

int SideOfLine(Point p, Line l) {
    return SideOfLine(p, l.a, l.b);
}

bool PointInSeg(Point p, Line l) {
    double tmp = (l.a - p) ^ (l.a - l.b);
    if (!epssgn(tmp) == 0) return false;
    if (epssgn(min(l.a.x, l.b.x) - p.x) <= 0 &&
        epssgn(p.x - max(l.a.x, l.b.x)) <= 0 &&
        epssgn(min(l.a.y, l.b.y) - p.y) <= 0 &&
        epssgn(p.y - max(l.a.y, l.b.y)) <= 0)
        return true;
    return false;
}

pair<int, Point> SegCrossSeg(Line s1, Line s2) {
    Point p1 = s1.a;
    Point p2 = s1.b;
    Point p3 = s2.a;
    Point p4 = s2.b;
    double a1 = area(p3 - p1, p4 - p1);
    double a2 = area(p4 - p2, p3 - p2);
    Point crossPoint = p1 + (p2 - p1)*(a1 / (a1 + a2));
    if (epssgn(((p2 - p1) ^ (p3 - p1))*((p2 - p1) ^ (p4 - p1))) < 0 &&
        epssgn(((p4 - p3) ^ (p1 - p3))*((p4 - p3) ^ (p2 - p3))) < 0)
        return make_pair(0, crossPoint); // standard cross
    if (epssgn((p2 - p1) ^ (p3 - p4)) != 0) {
        // 端点重合，不平行，不共线
        if (p1 == p3 || p1 == p4) return make_pair(1, p1);
        if (p2 == p3 || p2 == p4) return make_pair(1, p2);
        // s1端点在s2内部，不平行，不共线
        if (PointInSeg(p1, s2)) return make_pair(2, p1);
        if (PointInSeg(p2, s2)) return make_pair(2, p2);
        // s2端点在s1内部，不平行，不共线
        if (PointInSeg(p3, s1)) return make_pair(3, p3);
        if (PointInSeg(p4, s1)) return make_pair(3, p4);
        // s2所在直线与线段s1相交
        if (PointInSeg(crossPoint, s1)) return make_pair(8, crossPoint);
        // s1所在直线与线段s2相交
        if (PointInSeg(crossPoint, s2)) return make_pair(9, crossPoint);
        // 两直线相交
        return make_pair(4, crossPoint);
    }
    // 平行
    if (!epssgn(dist(p1, s2))) return make_pair(5, Point(0, 0)); 
    // 共线，有公共交点
    if (PointInSeg(p1, s2)) return make_pair(6, p1);
    if (PointInSeg(p2, s2)) return make_pair(6, p2);
    if (PointInSeg(p3, s1)) return make_pair(6, p3);
    if (PointInSeg(p4, s1)) return make_pair(6, p4);
    // 共线，无公共交点
    return make_pair(7, Point(0, 0));
}

// HalfPlane, cut src with Line a->b's left half plane.
typedef vector<Point> Polygon;
int cutPolygon(const Polygon& src, Point a, Point b, Polygon& res) {
    int n = src.size();
    res.clear();
    for (int i = 0; i < n; i++) {
        Point c = src[i];
        Point d = src[(i + 1) % n]; // note %
        if (epssgn((b - a) ^ (c - a)) >= 0) res.push_back(c);
        pair<int, Point> r = SegCrossSeg(Line(c, d), Line(a, b));
        if (r.first == 0 || r.first == 8 || r.first == 3) res.push_back(r.second);
    }
    return res.size();
}

int N, x, y;
Polygon island, res;

bool check(double mid) {
    vector<Line> shrink;
    for (int i = 0; i < N; i++) {
        Line l(island[i], island[(i + 1) % N]);
        Vector vl = island[(i + 1) % N] - island[i];
        Vector v = unit(Vector(-vl.y, vl.x)) * mid; // vertical, length=mid
        Line ll(l.a + v, l.b + v); // push in
        shrink.push_back(ll);
    }
    int s;
    Polygon tmp = island;
    for (int i = 0; i < shrink.size(); i++) {
        s = cutPolygon(tmp, shrink[i].a, shrink[i].b, res);
        if (s == 0) break;
        tmp = res;
    }
    //cout <<"check " <<mid<<" :"<< res.size() << endl;
    return res.size() > 0;
}

int main() {
    while (cin >> N && N) {
        island.clear();
        for (int i = 0; i < N; i++) {
            cin >> x >> y;
            island.push_back(Point(x, y));
        }
        // eps binary search
        double left = 0, right = inf;
        while (epssgn(left-right)<0) {
            double mid = (left + right) / 2;
            if (check(mid)) left = mid + eps;
            else right = mid;
        }
        cout << fixed << setprecision(6) << left - eps << endl;
    }
}

Pipe

#include <iostream>
#include <vector>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <cstring>

using namespace std;

const double inf = 1e9;
const double eps = 1e-6;

struct Point {
    double x, y;
    Point(double a = 0, double b = 0) { x = a; y = b; }
    bool operator == (const Point& b) const {
        return x == b.x && y == b.y;
    }
    bool operator < (const Point& b) const {
        if (x == b.x) return y < b.y;
        return x < b.x;
    }
    friend ostream& operator << (ostream& os, const Point& p) {
        os << "(" << p.x << ", " << p.y << ")";
        return os;
    }
};

typedef Point Vector;

Vector operator + (Point a, Point b) { return Vector(a.x + b.x, a.y + b.y); }
Vector operator - (Point a, Point b) { return Vector(a.x - b.x, a.y - b.y); }
Vector operator * (Point a, double k) { return Vector(a.x*k, a.y*k); }
Vector operator * (double k, Point a) { return Vector(a.x*k, a.y*k); }
Vector operator / (Point a, double k) { return Vector(a.x / k, a.y / k); }
double operator * (Vector a, Vector b) { return a.x*b.x + a.y*b.y; }
double operator ^ (Vector a, Vector b) { return a.x*b.y - b.x*a.y; }
double len(Vector a) { return sqrt(a.x*a.x + a.y*a.y); }
Vector unit(Vector p) { return p * (1 / len(p)); }
double project(Vector a, Vector b) { return a * unit(b);}

struct Line {
    Point a, b;
    Line() {}
    Line(Point a, Point b) :a(a), b(b) {}
    double getx(double y) { return (y - a.y) / (b.y - a.y)*(b.x - a.x) + a.x; }
    double gety(double x) { return (x - a.x) / (b.x - a.x)*(b.y - a.y) + a.y; }
    friend ostream& operator <<(ostream& os, const Line & l){
        os << l.a << "->" << l.b;
        return os;
    }
};

int epssgn(double x) {
    if (fabs(x) < eps) return 0;
    else return x < 0 ? -1 : 1;
}

double dist(Point x, Point y) { return len(x - y); }
double dist(Point p, Line l) { return fabs((p - l.a) ^ (l.b - l.a)) / len(l.b - l.a);}
double area(Vector a, Vector b) { return a ^ b / 2;}

int SideOfLine(Point p, Point a, Point b) {
    double res = (b - a) ^ (p - a);
    if (epssgn(res) == 0) return 0;
    else if (res > 0) return 1;
    else return -1;
}

int SideOfLine(Point p, Line l) {
    return SideOfLine(p, l.a, l.b);
}

bool PointInSeg(Point p, Line l) {
    double tmp = (l.a - p) ^ (l.a - l.b);
    if (!epssgn(tmp) == 0) return false;
    if (epssgn(min(l.a.x, l.b.x) - p.x) <= 0 &&
        epssgn(p.x - max(l.a.x, l.b.x)) <= 0 &&
        epssgn(min(l.a.y, l.b.y) - p.y) <= 0 &&
        epssgn(p.y - max(l.a.y, l.b.y)) <= 0)
        return true;
    return false;
}

pair<int, Point> SegCrossSeg(Line s1, Line s2) {
    Point p1 = s1.a;
    Point p2 = s1.b;
    Point p3 = s2.a;
    Point p4 = s2.b;
    double a1 = area(p3 - p1, p4 - p1);
    double a2 = area(p4 - p2, p3 - p2);
    Point crossPoint = p1 + (p2 - p1)*(a1 / (a1 + a2));
    if (epssgn(((p2 - p1) ^ (p3 - p1))*((p2 - p1) ^ (p4 - p1))) < 0 &&
        epssgn(((p4 - p3) ^ (p1 - p3))*((p4 - p3) ^ (p2 - p3))) < 0)
        return make_pair(0, crossPoint); // standard cross
    if (epssgn((p2 - p1) ^ (p3 - p4)) != 0) {
        // 端点重合，不平行，不共线
        if (p1 == p3 || p1 == p4) return make_pair(1, p1);
        if (p2 == p3 || p2 == p4) return make_pair(1, p2);
        // s1端点在s2内部，不平行，不共线
        if (PointInSeg(p1, s2)) return make_pair(2, p1);
        if (PointInSeg(p2, s2)) return make_pair(2, p2);
        // s2端点在s1内部，不平行，不共线
        if (PointInSeg(p3, s1)) return make_pair(3, p3);
        if (PointInSeg(p4, s1)) return make_pair(3, p4);
        // s2所在直线与线段s1相交
        if (PointInSeg(crossPoint, s1)) return make_pair(8, crossPoint);
        // s1所在直线与线段s2相交
        if (PointInSeg(crossPoint, s2)) return make_pair(9, crossPoint);
        // 两直线相交
        return make_pair(4, crossPoint);
    }
    // 平行
    if (!epssgn(dist(p1, s2))) return make_pair(5, Point(0, 0)); 
    // 共线，有公共交点
    if (PointInSeg(p1, s2)) return make_pair(6, p1);
    if (PointInSeg(p2, s2)) return make_pair(6, p2);
    if (PointInSeg(p3, s1)) return make_pair(6, p3);
    if (PointInSeg(p4, s1)) return make_pair(6, p4);
    // 共线，无公共交点
    return make_pair(7, Point(0, 0));
}

const int maxn = 25;
Point up[maxn], down[maxn];
int N;
double x, y;

int main() {
    while (cin >> N && N) {
        for (int i = 1; i <= N; i++) {
            cin >> x >> y;
            up[i] = Point(x, y);
            down[i] = Point(x, y - 1);
        }
        double mxx = -inf;
        bool all = false;
        int i, j, k;
        for (i = 1; i <= N; i++) {
            for (j = 1; j <= N; j++) {
                if (i == j) continue;
                Line l(up[i], down[j]);
                for (k = 1; k <= N; k++) {
                    Line seg(up[k], down[k]);
                    if (!LineCrossSeg(l, seg).first) break;
                }
                if (k > N) {
                    all = true;
                    break;
                }
                else if (k > max(i, j)) {
                    Line seg1(up[k], up[k - 1]);
                    pair<int, Point> res = SegCrossSeg(l, seg1);
                    if (res.first <= 3 || res.first == 6 || res.first == 9) 
                        mxx = max(mxx, res.second.x);
                    Line seg2(down[k], down[k - 1]);
                    res = SegCrossSeg(l, seg2);
                    if (res.first <= 3 || res.first == 6 || res.first == 9) 
                        mxx = max(mxx, res.second.x);
                }
            }
            if (all) break;
        }
        if (all) cout << "Through all the pipe." << endl;
        else cout << fixed << setprecision(2) << mxx << endl;
    }
}