# Inheritance

## 题目描述

The old King decided to divide the Kingdom into parts among his three sons. Each part is a polygonal area. Taking into account the bad temper of the middle son the King gave him a part of Kingdom such that moving straight from any place of this part to any other place of this part he will not cross the boundary.
There are several mineral deposits in the Kingdom. Each mineral deposit looks like a straight line segment. The middle son wants to know what part of mineral deposits is located inside his territory (not including the boundaries).

## 代码

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

static const double EPS = 1e-6;
int cmp(double a, double b) { return fabs(a - b) < EPS ? 0 : a < b ? -1 : 1; }

struct Point {
double x, y;
Point(double _x = 0, double _y = 0) : x(_x), y(_y) {};
bool operator < (const Point &p) const { return ! cmp(x, p.x) ? cmp(y, p.y) == -1 : cmp(x, p.x) == -1; }
Point operator + (const Point &p) const { return Point(x + p.x, y + p.y); }
Point operator - (const Point &p) const { return Point(x - p.x, y - p.y); }
Point operator * (const double &a) const { return Point(x * a, y * a); }
Point operator / (const double &a) const { return Point(x / a, y / a); }
double operator * (const Point &p) const { return x * p.y - y * p.x; }
double operator ! () const { return sqrt(x * x + y * y); }
};

struct Line {
Point a, b;
Line(Point _a = Point(), Point _b = Point()) : a(_a), b(_b) {}
bool operator | (const Line &l) const { return ! cmp((b - a) * (l.b - l.a), 0); }
Point operator & (const Line &l) const {
double t = (a - l.a) * (l.a - l.b) / ((a - b) * (l.a - l.b));
return a + (b - a) * t;
}
};

struct Solver {
private:
static const int N = 410;
int n, q, top;
Point point[N], sta[N];
vector <Point> poly;
void input() {
scanf("%d", &n);
for (int i = 1; i <= n; ++ i) scanf("%lf%lf", &point[i].x, &point[i].y);
scanf("%d", &q);
}
void init() {
sort(point + 1, point + n + 1);
for (int i = 1; i <= n; ++ i) {
while (top > 1 && cmp((sta[top] - sta[top - 1]) * (point[i] - sta[top]), 0) < 1) -- top;
sta[++ top] = point[i];
}
for (int i = 1; i <= top; ++ i) poly.push_back(sta[i]); top = 0;
for (int i = n; i; -- i){
while (top > 1 && cmp((sta[top] - sta[top - 1]) * (point[i] - sta[top]), 0) < 1) -- top;
sta[++ top] = point[i];
}
for (int i = 2; i < top; ++ i) poly.push_back(sta[i]);
}
bool in(Point p) {
for (int i = 0; i < poly.size(); ++ i)
if (cmp((poly[(i + 1) % poly.size()] - poly[i]) * (p - poly[i]), 0) < 0) return false;
return true;
}
void process() {
Line l;
scanf("%lf%lf%lf%lf", &l.a.x, &l.a.y, &l.b.x, &l.b.y);
for (int i = 0; i < poly.size(); ++ i) {
Line tmp(poly[i], poly[(i + 1) % poly.size()]);
if (! cmp((l.b - l.a) * (tmp.a - l.a), 0) && ! cmp((l.b - l.a) * (tmp.b - l.a), 0)) {
printf("0.00\n"); return;
}
}
vector <Point> inter;
for (int i = 0; i < poly.size(); ++ i)
if (! (Line(poly[i], poly[(i + 1) % poly.size()]) | l)) {
Line tmp = Line(poly[i], poly[(i + 1) % poly.size()]);
Point p = tmp & l;
if ((cmp(p.x, l.a.x) || cmp(p.y, l.a.y)) && (cmp(p.x, l.b.x) || cmp(p.y, l.b.y)) && cmp(min(l.a.x, l.b.x), p.x) < 1 && cmp(p.x, max(l.a.x, l.b.x)) < 1 && cmp(min(l.a.y, l.b.y), p.y) < 1 && cmp(p.y, max(l.a.y, l.b.y)) < 1 && cmp(min(tmp.a.x, tmp.b.x), p.x) < 1 && cmp(p.x, max(tmp.a.x, tmp.b.x)) < 1 && cmp(min(tmp.a.y, tmp.b.y), p.y) < 1 && cmp(p.y, max(tmp.a.y, tmp.b.y)) < 1) {
for (int j = 0; j < inter.size(); ++ j) if (! cmp(inter[j].x, p.x) && ! cmp(inter[j].y, p.y)) goto label;
inter.push_back(p);
}
label: ;
}
for (int i = 0; i < poly.size(); ++ i) {
Line tmp(poly[i], poly[(i + 1) % poly.size()]);
if (! cmp((l.b - l.a) * (tmp.a - l.a), 0) && ! cmp((l.b - l.a) * (tmp.b - l.a), 0)) {
printf("0.00\n"); return;
}
}
if (inter.empty())
if (in(l.a) && in(l.b)) printf("%.2lf\n", ! (l.b - l.a));
else printf("0.00\n");
else if (inter.size() == 2) printf("%.2lf\n", ! (inter[1] - inter[0]));
else if (in(l.a)) printf("%.2lf\n", ! (inter[0] - l.a));
else if (in(l.b)) printf("%.2lf\n", ! (inter[0] - l.b));
else printf("0.00\n");
}

public:
void solve() { input(), init(); while (q --) process(); }
} solver;

int main() {
solver.solve();
return 0;
}


418 I'm a teapot