一二象限有很多光源（点）和挡板（线段），问(x)轴上阴影的长度
#include <bits/stdc++.h>
using namespace std;
typedef pair<double, double> pdd;
const double eps = 1e-10;
const double inf = 1e18;
int sgn(double x) { return fabs(x) < eps ? 0 : (x > 0 ? 1 : -1); };
struct Point {
double x, y;
Point(){};
Point(double _x, double _y) {
x = _x;
y = _y;
}
int input() {
return scanf("%lf%lf", &x, &y);
}
double len() {
return hypot(x, y);
}
double len2() {
return x * x + y * y;
}
Point operator+(const Point &b) const {
return Point(x + b.x, y + b.y);
}
Point operator-(const Point &b) const {
return Point(x - b.x, y - b.y);
}
double operator^(const Point &b) const {
return x * b.y - y * b.x;
}
double operator*(const Point &b) const {
return x * b.x + y * b.y;
}
Point operator*(const double &k) const {
return Point(x * k, y * k);
}
Point operator/(const double &k) const {
return Point(x / k, y / k);
}
Point trunc(double r) {
double l = len();
if (!sgn(l)) return *this;
r /= l;
return Point(x * r, y * r);
}
double rad(Point a, Point b) {
Point p = *this;
return fabs(atan2(fabs((a - p) ^ (b - p)), (a - p) * (b - p)));
}
double distance(Point p) {
return hypot(x - p.x, y - p.y);
}
};
struct Line {
Point s, e;
Line(){};
Line(Point _s, Point _e) {
s = _s;
e = _e;
}
void input() {
s.input();
e.input();
}
double length() {
return s.distance(e);
}
bool pointonseg(Point p) {
return !sgn((p - s) ^ (e - s)) && sgn((p - s) * (p - e)) <= 0;
}
double dispointtoline(Point p) {
return fabs((p - s) ^ (e - s)) / length();
}
Point lineprog(Point p) {
return s + (((e - s) * ((e - s) * (p - s))) / ((e - s).len2()));
}
Point crosspoint(Line v) {
double a1 = (v.e - v.s) ^ (s - v.s);
double a2 = (v.e - v.s) ^ (e - v.s);
return Point((s.x * a2 - e.x * a1) / (a2 - a1), (s.y * a2 - e.y * a1) / (a2 - a1));
}
};
Point p[510];
Line l[510];
int vis[510];
vector<pdd> ve, now, last;
int main() {
Line xx = Line(Point(0, 0), Point(1, 0));
int t, n, m;
scanf("%d", &t);
while (t--) {
memset(vis, 0, sizeof(vis));
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) p[i].input();
for (int i = 0; i < m; i++) l[i].input();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (l[j].pointonseg(p[i])) {
vis[i] = 1;
break;
}
}
}
int flag = 0;
last.clear();
last.push_back(pdd(-inf, inf));
for (int i = 0; i < n; i++) {
if (vis[i]) continue;
ve.clear();
for (int j = 0; j < m; j++) {
if (sgn(l[j].s.y - l[j].e.y) == 0 && sgn(l[j].s.y - p[i].y) == 0) continue;
if (sgn(l[j].s.y - p[i].y) < 0 && sgn(l[j].e.y - p[i].y) < 0) {
Line l1 = Line(l[j].s, p[i]);
Line l2 = Line(l[j].e, p[i]);
double x1 = xx.crosspoint(l1).x;
double x2 = xx.crosspoint(l2).x;
if (x1 > x2) swap(x1, x2);
ve.push_back(pdd(x1, x2));
}
else if (sgn(l[j].s.y - p[i].y) < 0) {
if (sgn((p[i] - l[j].s) ^ (l[j].e - l[j].s)) > 0) {
Line l1 = Line(p[i], l[j].s);
double x1 = xx.crosspoint(l1).x;
ve.push_back(pdd(-inf, x1));
}
else {
Line l1 = Line(p[i], l[j].s);
double x1 = xx.crosspoint(l1).x;
ve.push_back(pdd(x1, inf));
}
}
else if (sgn(l[j].e.y - p[i].y) < 0) {
if (sgn((p[i] - l[j].e) ^ (l[j].s - l[j].e)) > 0) {
Line l1 = Line(p[i], l[j].e);
double x1 = xx.crosspoint(l1).x;
ve.push_back(pdd(-inf, x1));
}
else {
Line l1 = Line(p[i], l[j].e);
double x1 = xx.crosspoint(l1).x;
ve.push_back(pdd(x1, inf));
}
}
}
now.clear();
sort(ve.begin(), ve.end());
int sz = ve.size();
if (!sz) {
flag = 1;
break;
}
double ll = ve[0].first, rr = ve[0].second;
for (int i = 1; i < sz; i++) {
if (sgn(ve[i].first - rr) <= 0) {
rr = max(rr, ve[i].second);
continue;
}
now.push_back(pdd(ll, rr));
ll = ve[i].first;
rr = ve[i].second;
}
now.push_back(pdd(ll, rr));
ve.clear();
int a = now.size();
int b = last.size();
int ia = 0, ib = 0;
while (ia < a && ib < b) {
ll = max(now[ia].first, last[ib].first);
rr = min(now[ia].second, last[ib].second);
if (sgn(rr - ll) > 0) ve.push_back(pdd(ll, rr));
if (sgn(now[ia].second - last[ib].second) > 0) ib++;
else ia++;
}
last = ve;
}
if (flag) {
puts("0.0000000000");
continue;
}
double ans = 0;
for (auto i : last) {
ans += i.second - i.first;
if (sgn(ans - 1e9) > 0) break;
}
if (sgn(ans - 1e9) > 0) puts("-1");
else printf("%.10f
", ans);
}
return 0;
}