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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
| #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;
}
|