firiexp's Library
This documentation is automatically generated by online-judge-tools/verification-helper
test/aoj_cgl_4_c_half_plane_intersection.test.cpp
- View this file on GitHub
- Last update: 2026-03-22 11:58:39+09:00
- Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_4_C
Depends on
- 幾何ライブラリ(Geometry)
(geometry/geometry.cpp)
- 半平面共通部分(Half-Plane Intersection)
(geometry/half_plane_intersection.cpp)
- 高速入出力(Fast IO)
(util/fastio.cpp)
Code
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_4_C"
#define ERROR "1e-8"
#include <algorithm>
#include <cassert>
#include <cmath>
#include <deque>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
#include <cstdio>
#include <cstring>
#include <string>
#include <type_traits>
#include "../util/fastio.cpp"
#include "../geometry/half_plane_intersection.cpp"
vector<Line> polygon_half_planes(const Polygon &poly) {
vector<Line> ls;
int n = poly.size();
ls.reserve(n);
for (int i = 0; i < n; ++i) {
ls.emplace_back(poly[i], poly[(i + 1) % n]);
}
return ls;
}
void self_check() {
{
Polygon poly = {
Point(1, 1),
Point(4, 1),
Point(4, 3),
Point(1, 3),
};
auto ls = polygon_half_planes(poly);
ls.emplace_back(Point(2, 0), Point(2, 4));
Polygon got = half_plane_intersection(ls);
assert(fabs(fabs(area(got)) - 2.0) < 1e-9);
}
{
Polygon poly = {
Point(1, 1),
Point(4, 1),
Point(4, 3),
Point(1, 3),
};
auto ls = polygon_half_planes(poly);
ls.emplace_back(Point(2, 4), Point(2, 0));
Polygon got = half_plane_intersection(ls);
assert(fabs(fabs(area(got)) - 4.0) < 1e-9);
}
{
Polygon poly = {
Point(0, 0),
Point(4, 0),
Point(4, 2),
Point(2, 4),
Point(0, 4),
};
auto ls = polygon_half_planes(poly);
ls.emplace_back(Point(5, 5), Point(5, 3));
Polygon got = half_plane_intersection(ls);
assert(got.empty());
}
}
int main() {
self_check();
Scanner sc;
int n;
sc.read(n);
Polygon poly(n);
for (int i = 0; i < n; ++i) {
ll x, y;
sc.read(x, y);
poly[i] = Point(x, y);
}
vector<Line> base = polygon_half_planes(poly);
int q;
sc.read(q);
while (q--) {
ll x1, y1, x2, y2;
sc.read(x1, y1, x2, y2);
vector<Line> ls = base;
ls.emplace_back(Point(x1, y1), Point(x2, y2));
Polygon ans = half_plane_intersection(ls);
printf("%.8f\n", fabs(area(ans)));
}
return 0;
}#line 1 "test/aoj_cgl_4_c_half_plane_intersection.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_4_C"
#define ERROR "1e-8"
#include <algorithm>
#include <cassert>
#include <cmath>
#include <deque>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
#include <cstdio>
#include <cstring>
#include <string>
#include <type_traits>
#line 1 "util/fastio.cpp"
using namespace std;
extern "C" int fileno(FILE *);
extern "C" int isatty(int);
template<class T, class = void>
struct is_fastio_range : false_type {};
template<class T>
struct is_fastio_range<T, void_t<decltype(declval<T &>().begin()), decltype(declval<T &>().end())>> : true_type {};
template<class T, class = void>
struct has_fastio_value : false_type {};
template<class T>
struct has_fastio_value<T, void_t<decltype(declval<const T &>().value())>> : true_type {};
struct FastIoDigitTable {
char num[40000];
constexpr FastIoDigitTable() : num() {
for (int i = 0; i < 10000; ++i) {
int x = i;
for (int j = 3; j >= 0; --j) {
num[i * 4 + j] = char('0' + x % 10);
x /= 10;
}
}
}
};
struct Scanner {
static constexpr int BUFSIZE = 1 << 17;
static constexpr int OFFSET = 64;
char buf[BUFSIZE + 1];
int idx, size;
bool interactive;
Scanner() : idx(0), size(0), interactive(isatty(fileno(stdin))) {}
inline void load() {
int len = size - idx;
memmove(buf, buf + idx, len);
if (interactive) {
if (fgets(buf + len, BUFSIZE + 1 - len, stdin)) size = len + (int)strlen(buf + len);
else size = len;
} else {
size = len + (int)fread(buf + len, 1, BUFSIZE - len, stdin);
}
idx = 0;
buf[size] = 0;
}
inline void ensure() {
if (idx + OFFSET > size) load();
}
inline void ensure_interactive() {
if (idx == size) load();
}
inline char skip() {
if (interactive) {
ensure_interactive();
while (buf[idx] && buf[idx] <= ' ') {
++idx;
ensure_interactive();
}
return buf[idx++];
}
ensure();
while (buf[idx] && buf[idx] <= ' ') {
++idx;
ensure();
}
return buf[idx++];
}
template<class T, typename enable_if<is_integral<T>::value, int>::type = 0>
void read(T &x) {
if (interactive) {
char c = skip();
bool neg = false;
if constexpr (is_signed<T>::value) {
if (c == '-') {
neg = true;
ensure_interactive();
c = buf[idx++];
}
}
x = 0;
while (c >= '0') {
x = x * 10 + (c & 15);
ensure_interactive();
c = buf[idx++];
}
if constexpr (is_signed<T>::value) {
if (neg) x = -x;
}
return;
}
char c = skip();
bool neg = false;
if constexpr (is_signed<T>::value) {
if (c == '-') {
neg = true;
c = buf[idx++];
}
}
x = 0;
while (c >= '0') {
x = x * 10 + (c & 15);
c = buf[idx++];
}
if constexpr (is_signed<T>::value) {
if (neg) x = -x;
}
}
template<class T, typename enable_if<!is_integral<T>::value && !is_fastio_range<T>::value && !is_same<typename decay<T>::type, string>::value && has_fastio_value<T>::value, int>::type = 0>
void read(T &x) {
long long v;
read(v);
x = T(v);
}
template<class Head, class Next, class... Tail>
void read(Head &head, Next &next, Tail &...tail) {
read(head);
read(next, tail...);
}
template<class T, class U>
void read(pair<T, U> &p) {
read(p.first, p.second);
}
template<class T, typename enable_if<is_fastio_range<T>::value && !is_same<typename decay<T>::type, string>::value, int>::type = 0>
void read(T &a) {
for (auto &x : a) read(x);
}
void read(char &c) {
c = skip();
}
void read(string &s) {
s.clear();
if (interactive) {
ensure_interactive();
while (buf[idx] && buf[idx] <= ' ') {
++idx;
ensure_interactive();
}
while (true) {
int start = idx;
while (idx < size && buf[idx] > ' ') ++idx;
s.append(buf + start, idx - start);
if (idx < size) break;
load();
if (size == 0) break;
}
if (idx < size) ++idx;
return;
}
ensure();
while (buf[idx] && buf[idx] <= ' ') {
++idx;
ensure();
}
while (true) {
int start = idx;
while (idx < size && buf[idx] > ' ') ++idx;
s.append(buf + start, idx - start);
if (idx < size) break;
load();
}
if (idx < size) ++idx;
}
};
struct Printer {
static constexpr int BUFSIZE = 1 << 17;
static constexpr int OFFSET = 64;
char buf[BUFSIZE];
int idx;
bool interactive;
inline static constexpr FastIoDigitTable table{};
Printer() : idx(0), interactive(isatty(fileno(stdout))) {}
~Printer() { flush(); }
inline void flush() {
if (idx) {
fwrite(buf, 1, idx, stdout);
idx = 0;
}
}
inline void pc(char c) {
if (idx > BUFSIZE - OFFSET) flush();
buf[idx++] = c;
if (interactive && c == '\n') flush();
}
inline void print_range(const char *s, size_t n) {
size_t pos = 0;
while (pos < n) {
if (idx == BUFSIZE) flush();
size_t chunk = min(n - pos, (size_t)(BUFSIZE - idx));
memcpy(buf + idx, s + pos, chunk);
idx += (int)chunk;
pos += chunk;
}
}
void print(const char *s) {
print_range(s, strlen(s));
}
void print(const string &s) {
print_range(s.data(), s.size());
}
void print(char c) {
pc(c);
}
void print(bool b) {
pc(char('0' + (b ? 1 : 0)));
}
template<class T, typename enable_if<is_integral<T>::value && !is_same<T, bool>::value, int>::type = 0>
void print(T x) {
if (idx > BUFSIZE - 100) flush();
using U = typename make_unsigned<T>::type;
U y;
if constexpr (is_signed<T>::value) {
if (x < 0) {
buf[idx++] = '-';
y = U(0) - static_cast<U>(x);
} else {
y = static_cast<U>(x);
}
} else {
y = x;
}
if (y == 0) {
buf[idx++] = '0';
return;
}
static constexpr int TMP_SIZE = sizeof(U) * 10 / 4;
char tmp[TMP_SIZE];
int pos = TMP_SIZE;
while (y >= 10000) {
pos -= 4;
memcpy(tmp + pos, table.num + (y % 10000) * 4, 4);
y /= 10000;
}
if (y >= 1000) {
memcpy(buf + idx, table.num + (y << 2), 4);
idx += 4;
} else if (y >= 100) {
memcpy(buf + idx, table.num + (y << 2) + 1, 3);
idx += 3;
} else if (y >= 10) {
unsigned q = (unsigned(y) * 205) >> 11;
buf[idx] = char('0' + q);
buf[idx + 1] = char('0' + (unsigned(y) - q * 10));
idx += 2;
} else {
buf[idx++] = char('0' + y);
}
memcpy(buf + idx, tmp + pos, TMP_SIZE - pos);
idx += TMP_SIZE - pos;
}
template<class T, typename enable_if<!is_integral<T>::value && !is_fastio_range<T>::value && !is_same<typename decay<T>::type, string>::value && has_fastio_value<T>::value, int>::type = 0>
void print(const T &x) {
print(x.value());
}
template<class T, typename enable_if<is_fastio_range<T>::value && !is_same<typename decay<T>::type, string>::value, int>::type = 0>
void print(const T &a) {
bool first = true;
for (auto &&x : a) {
if (!first) pc(' ');
first = false;
print(x);
}
}
template<class T>
void println(const T &x) {
print(x);
pc('\n');
}
template<class Head, class... Tail>
void println(const Head &head, const Tail &...tail) {
print(head);
((pc(' '), print(tail)), ...);
pc('\n');
}
void println() {
pc('\n');
}
};
template<class T>
Scanner &operator>>(Scanner &in, T &x) {
in.read(x);
return in;
}
template<class T>
Printer &operator<<(Printer &out, const T &x) {
out.print(x);
return out;
}
/**
* @brief 高速入出力(Fast IO)
*/
#line 1 "geometry/geometry.cpp"
// 凸包は同じ頂点が含まれているとバグる
using real = double;
static constexpr real EPS = 1e-10;
const real pi = acos(-1);
struct Point {
real x, y;
Point& operator+=(const Point a) { x += a.x; y += a.y; return *this; }
Point& operator-=(const Point a) { x -= a.x; y -= a.y; return *this; }
Point& operator*=(const real k) { x *= k; y *= k; return *this; }
Point& operator/=(const real k) { x /= k; y /= k; return *this; }
Point operator+(const Point a) const {return Point(*this) += a; }
Point operator-(const Point a) const {return Point(*this) -= a; }
Point operator*(const real k) const {return Point(*this) *= k; }
Point operator/(const real k) const {return Point(*this) /= k; }
bool operator<(const Point &a) const { return (x != a.x ? x < a.x : y < a.y); }
explicit Point(real a = 0, real b = 0) : x(a), y(b) {};
};
bool sorty(Point a, Point b) {
return (a.y != b.y ? a.y < b.y : a.x < b.x);
}
istream &operator>>(istream &s, Point &P) {
s >> P.x >> P.y;
return s;
}
inline real dot(Point a, Point b) { return a.x * b.x + a.y * b.y; }
inline real cross(Point a, Point b) { return a.x * b.y - a.y * b.x; }
inline real abs(Point a) { return sqrt(dot(a, a)); }
real angle(Point A, Point B) {
return acos(dot(A, B) / abs(A) / abs(B));
}
static constexpr int COUNTER_CLOCKWISE = 1;
static constexpr int CLOCKWISE = -1;
static constexpr int ONLINE_BACK = 2;
static constexpr int ONLINE_FRONT = -2;
static constexpr int ON_SEGMENT = 0;
int ccw(Point a, Point b, Point c) {
b -= a;
c -= a;
if (cross(b, c) > EPS)
return COUNTER_CLOCKWISE;
if (cross(b, c) < -EPS)
return CLOCKWISE;
if (dot(b, c) < 0)
return ONLINE_BACK;
if (abs(b) < abs(c))
return ONLINE_FRONT;
return ON_SEGMENT;
}
struct Segment {
Point a, b;
Segment(Point x, Point y) : a(x), b(y) {};
};
struct Line {
Point a, b;
Line(Point x, Point y) : a(x), b(y) {};
};
struct Circle {
Point c;
real r;
Circle(Point c, real r) : c(c), r(r) {};
};
using Polygon = vector<Point>;
bool intersect(Segment s, Segment t) {
return (ccw(s.a, s.b, t.a) * ccw(s.a, s.b, t.b) <= 0 &&
ccw(t.a, t.b, s.a) * ccw(t.a, t.b, s.b) <= 0);
}
bool intersect(Segment s, Line t) {
int a = ccw(t.a, t.b, s.a), b = ccw(t.a, t.b, s.b);
return (!(a & 1) || !(b & 1) || a != b);
}
Point polar(double r, double t) {
return Point(r * cos(t), r * sin(t));
}
double arg(Point p) {
return atan2(p.y, p.x);
}
static constexpr int CONTAIN = 0;
static constexpr int INSCRIBE = 1;
static constexpr int INTERSECT = 2;
static constexpr int CIRCUMSCRIBED = 3;
static constexpr int SEPARATE = 4;
int intersect(Circle c1, Circle c2) {
if (c1.r < c2.r)
swap(c1, c2);
real d = abs(c1.c - c2.c);
real r = c1.r + c2.r;
if (fabs(d - r) < EPS)
return CIRCUMSCRIBED;
if (d > r)
return SEPARATE;
if (fabs(d + c2.r - c1.r) < EPS)
return INSCRIBE;
if (d + c2.r < c1.r)
return CONTAIN;
return INTERSECT;
}
real distance(Line l, Point c) {
return abs(cross(l.b - l.a, c - l.a) / abs(l.b - l.a));
}
real distance(Segment s, Point c) {
if (dot(s.b - s.a, c - s.a) < EPS)
return abs(c - s.a);
if (dot(s.a - s.b, c - s.b) < EPS)
return abs(c - s.b);
return abs(cross(s.b - s.a, c - s.a)) / abs(s.a - s.b);
}
real distance(Segment s, Segment t) {
if (intersect(s, t))
return 0.0;
return min({distance(s, t.a), distance(s, t.b),
distance(t, s.a), distance(t, s.b)});
}
Point project(Line l, Point p) {
Point Q = l.b - l.a;
return l.a + Q * (dot(p - l.a, Q) / dot(Q, Q));
}
Point project(Segment s, Point p) {
Point Q = s.b - s.a;
return s.a + Q * (dot(p - s.a, Q) / dot(Q, Q));
}
Point refrect(Segment s, Point p) {
Point Q = project(s, p);
return Q * 2 - p;
}
bool isOrthogonal(Segment s, Segment t) {
return fabs(dot(s.b - s.a, t.b - t.a)) < EPS;
}
bool isparallel(Segment s, Segment t) {
return fabs(cross(s.b - s.a, t.b - t.a)) < EPS;
}
Point crossPoint(Segment s, Segment t) {
real d1 = cross(s.b - s.a, t.b - t.a);
real d2 = cross(s.b - s.a, s.b - t.a);
if (fabs(d1) < EPS && fabs(d2) < EPS)
return t.a;
return t.a + (t.b - t.a) * d2 / d1;
}
Point crossPoint(Line s, Line t) {
real d1 = cross(s.b - s.a, t.b - t.a);
real d2 = cross(s.b - s.a, s.b - t.a);
if (fabs(d1) < EPS && fabs(d2) < EPS)
return t.a;
return t.a + (t.b - t.a) * d2 / d1;
}
Polygon crossPoint(Circle c, Line l) {
Point p = project(l, c.c), q = (l.b - l.a) / abs(l.b - l.a);
if (abs(distance(l, c.c) - c.r) < EPS) {
return {p};
}
double k = sqrt(c.r * c.r - dot(p - c.c, p - c.c));
return {p - q * k, p + q * k};
}
Polygon crossPoint(Circle c, Segment s) {
auto tmp = crossPoint(c, Line(s.a, s.b));
Polygon ret;
for (auto &&i: tmp) {
if (distance(s, i) < EPS)
ret.emplace_back(i);
}
return ret;
}
Polygon crossPoint(Circle c1, Circle c2) {
double d = abs(c1.c - c2.c);
double a = acos((c1.r * c1.r + d * d - c2.r * c2.r) / (2 * c1.r * d));
double t = arg(c2.c - c1.c);
return {c1.c + polar(c1.r, t + a), c1.c + polar(c1.r, t - a)};
}
Polygon tangent(Circle c1, Point p) {
Circle c2 = Circle(p, sqrt(dot(c1.c - p, c1.c - p) - c1.r * c1.r));
return crossPoint(c1, c2);
}
vector<Line> tangent(Circle c1, Circle c2) {
vector<Line> ret;
if (c1.r < c2.r)
swap(c1, c2);
double k = dot(c1.c - c2.c, c1.c - c2.c);
if (abs(k) < EPS)
return {};
Point u = (c2.c - c1.c) / sqrt(k);
Point v(-u.y, u.x);
for (auto &&i: {-1, 1}) {
double h = (c1.r + i * c2.r) / sqrt(k);
if (abs(h * h - 1) < EPS) {
ret.emplace_back(c1.c + u * c1.r, c1.c + (u + v) * c1.r);
} else if (h * h < 1) {
Point u2 = u * h, v2 = v * sqrt(1 - h * h);
ret.emplace_back(c1.c + (u2 + v2) * c1.r, c2.c - (u2 + v2) * c2.r * i);
ret.emplace_back(c1.c + (u2 - v2) * c1.r, c2.c - (u2 - v2) * c2.r * i);
}
}
return ret;
}
real area(Polygon v) {
if (v.size() < 3)
return 0.0;
real ans = 0.0;
for (int i = 0; i < v.size(); ++i) {
ans += cross(v[i], v[(i + 1) % v.size()]);
}
return ans / 2;
}
real area(Circle c, Polygon &v) {
int n = v.size();
real ans = 0.0;
Polygon u;
for (int i = 0; i < n; ++i) {
u.emplace_back(v[i]);
auto q = crossPoint(c, Segment(v[i], v[(i + 1) % n]));
for (auto &&j: q) {
u.emplace_back(j);
}
}
for (int i = 0; i < u.size(); ++i) {
Point A = u[i] - c.c, B = u[(i + 1) % u.size()] - c.c;
if (abs(A) >= c.r + EPS || abs(B) >= c.r + EPS) {
Point C = polar(1, arg(B) - arg(A));
ans += c.r * c.r * arg(C) / 2;
} else {
ans += cross(A, B) / 2;
}
}
return ans;
}
real area(Circle a, Circle b) {
auto d = abs(a.c - b.c);
if (a.r + b.r <= d + EPS)
return 0;
else if (d <= abs(a.r - b.r))
return pi * min(a.r, b.r) * min(a.r, b.r);
real p = 2 * acos((a.r * a.r + d * d - b.r * b.r) / (2 * a.r * d));
real q = 2 * acos((b.r * b.r + d * d - a.r * a.r) / (2 * b.r * d));
return a.r * a.r * (p - sin(p)) / 2 + b.r * b.r * (q - sin(q)) / 2;
}
Polygon convex_hull(Polygon v) {
int n = v.size();
sort(v.begin(), v.end(), sorty);
int k = 0;
Polygon ret(n * 2);
for (int i = 0; i < n; ++i) {
while (k > 1 && cross(ret[k - 1] - ret[k - 2], v[i] - ret[k - 1]) < 0)
k--;
ret[k++] = v[i];
}
for (int i = n - 2, t = k; i >= 0; i--) {
while (k > t && cross(ret[k - 1] - ret[k - 2], v[i] - ret[k - 1]) < 0)
k--;
ret[k++] = v[i];
}
ret.resize(k - 1);
return ret;
}
bool isconvex(Polygon v) {
int n = v.size();
for (int i = 0; i < n; ++i) {
if (ccw(v[(i + n - 1) % n], v[i], v[(i + 1) % n]) == CLOCKWISE)
return false;
}
return true;
}
int contains(Polygon v, Point p) {
int n = v.size();
bool x = false;
static constexpr int IN = 2, ON = 1, OUT = 0;
for (int i = 0; i < n; ++i) {
Point a = v[i] - p, b = v[(i + 1) % n] - p;
if (fabs(cross(a, b)) < EPS && dot(a, b) < EPS)
return ON;
if (a.y > b.y)
swap(a, b);
if (a.y < EPS && EPS < b.y && cross(a, b) > EPS)
x = !x;
}
return (x ? IN : OUT);
}
int contains_convex(Polygon &v, Point p) {
int a = 1, b = v.size() - 1;
static constexpr int IN = 2, ON = 1, OUT = 0;
if (v.size() < 3)
return (ccw(v.front(), v.back(), p) & 1) == 0 ? ON : OUT;
if (ccw(v[0], v[a], v[b]) > 0)
swap(a, b);
int la = ccw(v[0], v[a], p), lb = ccw(v[0], v[b], p);
if ((la & 1) == 0 || (lb & 1) == 0)
return ON;
if (la > 0 || lb < 0)
return OUT;
while (abs(a - b) > 1) {
int c = (a + b) / 2;
int val = ccw(v[0], v[c], p);
(val > 0 ? b : a) = c;
}
int res = ccw(v[a], v[b], p);
if ((res & 1) == 0)
return ON;
return res < 0 ? IN : OUT;
}
real diameter(Polygon v) {
int n = v.size();
if (n == 2)
return abs(v[0] - v[1]);
int i = 0, j = 0;
for (int k = 0; k < n; ++k) {
if (v[i] < v[k])
i = k;
if (!(v[j] < v[k]))
j = k;
}
real ret = 0;
int si = i, sj = j;
while (i != sj || j != si) {
ret = max(ret, abs(v[i] - v[j]));
if (cross(v[(i + 1) % n] - v[i], v[(j + 1) % n] - v[j]) < 0.0)
i = (i + 1) % n;
else
j = (j + 1) % n;
}
return ret;
}
Polygon convexCut(Polygon v, Line l) {
Polygon q;
int n = v.size();
for (int i = 0; i < n; ++i) {
Point a = v[i], b = v[(i + 1) % n];
if (ccw(l.a, l.b, a) != -1)
q.push_back(a);
if (ccw(l.a, l.b, a) * ccw(l.a, l.b, b) < 0) {
q.push_back(crossPoint(Line(a, b), l));
}
}
return q;
}
real closest_pair(Polygon &v, int l = 0, int r = -1) {
if (!(~r)) {
r = v.size();
sort(v.begin(), v.end());
}
if (r - l < 2) {
return abs(v.front() - v.back());
}
int mid = (l + r) / 2;
real p = v[mid].x;
real d = min(closest_pair(v, l, mid), closest_pair(v, mid, r));
inplace_merge(v.begin() + l, v.begin() + mid, v.begin() + r, sorty);
Polygon u;
for (int i = l; i < r; ++i) {
if (fabs(v[i].x - p) >= d)
continue;
for (int j = 0; j < u.size(); ++j) {
real dy = v[i].y - next(u.rbegin(), j)->y;
if (dy >= d)
break;
d = min(d, abs(v[i] - *next(u.rbegin(), j)));
}
u.emplace_back(v[i]);
}
return d;
}
/**
* @brief 幾何ライブラリ(Geometry)
*/
#line 2 "geometry/half_plane_intersection.cpp"
namespace internal_half_plane_intersection {
struct HalfPlane {
Point p, pq;
real angle;
HalfPlane() = default;
explicit HalfPlane(const Line &l)
: p(l.a), pq(l.b - l.a), angle(atan2(pq.y, pq.x)) {}
bool operator<(const HalfPlane &other) const {
if (fabs(angle - other.angle) > EPS) return angle < other.angle;
return cross(pq, other.p - p) < 0;
}
bool outside(Point r) const {
return cross(pq, r - p) < -EPS;
}
};
Point intersection(const HalfPlane &s, const HalfPlane &t) {
real a = cross(t.p - s.p, t.pq) / cross(s.pq, t.pq);
return s.p + s.pq * a;
}
bool same_point(Point a, Point b) {
return abs(a - b) < EPS;
}
} // namespace internal_half_plane_intersection
Polygon half_plane_intersection(vector<Line> ls) {
using namespace internal_half_plane_intersection;
static constexpr real INF = 1e9;
vector<HalfPlane> hs;
hs.reserve(ls.size() + 4);
for (const Line &l : ls) hs.emplace_back(l);
Polygon box = {
Point(-INF, -INF),
Point(INF, -INF),
Point(INF, INF),
Point(-INF, INF),
};
for (int i = 0; i < 4; ++i) {
hs.emplace_back(Line(box[i], box[(i + 1) % 4]));
}
sort(hs.begin(), hs.end());
deque<HalfPlane> deq;
for (const HalfPlane &h : hs) {
while (deq.size() > 1 &&
h.outside(intersection(deq.back(), deq[deq.size() - 2]))) {
deq.pop_back();
}
while (deq.size() > 1 &&
h.outside(intersection(deq[0], deq[1]))) {
deq.pop_front();
}
if (!deq.empty() && fabs(cross(deq.back().pq, h.pq)) < EPS) {
if (dot(deq.back().pq, h.pq) < 0) return {};
if (h.outside(deq.back().p)) deq.pop_back();
else continue;
}
deq.push_back(h);
}
while (deq.size() > 2 &&
deq.front().outside(intersection(deq.back(), deq[deq.size() - 2]))) {
deq.pop_back();
}
while (deq.size() > 2 &&
deq.back().outside(intersection(deq[0], deq[1]))) {
deq.pop_front();
}
if (deq.size() < 3) return {};
Polygon res;
res.reserve(deq.size());
for (int i = 0; i < (int)deq.size(); ++i) {
Point p = intersection(deq[i], deq[(i + 1) % deq.size()]);
if (res.empty() || !same_point(res.back(), p)) res.push_back(p);
}
if (res.size() >= 2 && same_point(res.front(), res.back())) res.pop_back();
if (res.size() < 3 || fabs(area(res)) < EPS) return {};
return res;
}
/**
* @brief 半平面共通部分(Half-Plane Intersection)
*/
#line 21 "test/aoj_cgl_4_c_half_plane_intersection.test.cpp"
vector<Line> polygon_half_planes(const Polygon &poly) {
vector<Line> ls;
int n = poly.size();
ls.reserve(n);
for (int i = 0; i < n; ++i) {
ls.emplace_back(poly[i], poly[(i + 1) % n]);
}
return ls;
}
void self_check() {
{
Polygon poly = {
Point(1, 1),
Point(4, 1),
Point(4, 3),
Point(1, 3),
};
auto ls = polygon_half_planes(poly);
ls.emplace_back(Point(2, 0), Point(2, 4));
Polygon got = half_plane_intersection(ls);
assert(fabs(fabs(area(got)) - 2.0) < 1e-9);
}
{
Polygon poly = {
Point(1, 1),
Point(4, 1),
Point(4, 3),
Point(1, 3),
};
auto ls = polygon_half_planes(poly);
ls.emplace_back(Point(2, 4), Point(2, 0));
Polygon got = half_plane_intersection(ls);
assert(fabs(fabs(area(got)) - 4.0) < 1e-9);
}
{
Polygon poly = {
Point(0, 0),
Point(4, 0),
Point(4, 2),
Point(2, 4),
Point(0, 4),
};
auto ls = polygon_half_planes(poly);
ls.emplace_back(Point(5, 5), Point(5, 3));
Polygon got = half_plane_intersection(ls);
assert(got.empty());
}
}
int main() {
self_check();
Scanner sc;
int n;
sc.read(n);
Polygon poly(n);
for (int i = 0; i < n; ++i) {
ll x, y;
sc.read(x, y);
poly[i] = Point(x, y);
}
vector<Line> base = polygon_half_planes(poly);
int q;
sc.read(q);
while (q--) {
ll x1, y1, x2, y2;
sc.read(x1, y1, x2, y2);
vector<Line> ls = base;
ls.emplace_back(Point(x1, y1), Point(x2, y2));
Polygon ans = half_plane_intersection(ls);
printf("%.8f\n", fabs(area(ans)));
}
return 0;
}