1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 310;
const double eps = 1e-8;
struct Point {
    double x, y;
    Point() {}
    Point(double x, double y): x(x), y(y) {}
    Point operator - (const Point& rhs) const {
        return Point(x-rhs.x, y-rhs.y);
    }
};
struct Line {
    double a, b, c;
    Line(const Point& p1, const Point& p2) {
        a = p2.y - p1.y, b = p1.x - p2.x, c = p1.y*p2.x - p1.x*p2.y;
    }
    pair<double, double> GetCross(const Line& rhs, int& ans) {
        ans = 1;
        double k = rhs.a*b-a*rhs.b;
        if (fabs(k) < eps) {
            ans = 0;
            return pair<double, double>(0, 0);
        }
        return pair<double, double>(-(b*rhs.c-rhs.b*c)/k, (a*rhs.c-rhs.a*c)/k);
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX