QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#673159#7511. Planar GraphNananiWA 1ms3828kbC++1720.7kb2024-10-24 20:49:132024-10-24 20:49:14

Judging History

你现在查看的是最新测评结果

  • [2024-10-24 20:49:14]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3828kb
  • [2024-10-24 20:49:13]
  • 提交

answer

//by 72
#include <bits/stdc++.h>
#define F(i, a, b) for(int i = a; i <= b; i ++)
#define Fd(i, a, b) for(int i = a; i >= b; i --)
#define pb push_back
#define pii pair<int, int>
#define fi first
#define se second
#define mp make_pair
// #define int long long
const int mod = 998244353;
const int inf = 1e9;
typedef long long ll;
typedef ll T;
// long long 类型可以把 fabs -> abs
typedef double db;
using namespace std;
const db pi = acosl(-1);
const db eps = 1e-8;
int sgn(T x) {
    if (fabs(x) < eps) return 0;
    else return x < 0 ? -1 : 1;
}
int dcmp(T x, T y) {
    if (fabs(x - y) < eps) return 0;
    else return x < y ? -1 : 1;
}
struct point {
    T x, y;
    point() {}
    point(T x, T y): x(x), y(y) {}
    point operator + (point B) const {return point(x + B.x, y + B.y);}
    point operator - (point B) const {return point(x - B.x, y - B.y);}
    point operator * (T k) const {return point(x * k, y * k);}
    point operator / (T k) const {return point(x / k, y / k);}
    bool operator == (point B) const {return sgn(x - B.x) == 0 && sgn(y - B.y) == 0;}
    bool operator < (point B) const {return sgn(x - B.x) < 0 || (sgn(x - B.x) == 0 && sgn(y - B.y) < 0);}
    T cross(point p) const {return x * p.y - y * p.x;} // 向量叉积
    int left(point p) const {return sgn(cross(p));} // 0共线 1 p在左边 -1 p在右边
};
db dis(point A, point B) {return sqrtl((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));}
typedef point vct;
T dot(vct A, vct B) {return A.x * B.x + A.y * B.y;}
db len(vct A) {return sqrtl(dot(A, A));}
T len2(vct A) {return dot(A, A);}
db angle(vct A, vct B) {
    db tmp = dot(A, B) / len(A) / len(B);
    if(tmp > 1) tmp = 1;
    else if(tmp < -1) tmp = -1;
    return acosl(tmp);
    // return atan2l(cross(A, B), dot(A, B));
} // 求向量a和b的夹角
T cross(vct A, vct B) {return A.x * B.y - A.y * B.x;}
T area2(point A, point B, point C) {return fabs(cross(B - A, C - A));}   //平行四边形面积
vct rotate(vct A, db rad) {return vct(A.x * cosl(rad) - A.y * sinl(rad), A.x * sinl(rad) + A.y * cosl(rad));}   //逆时针旋转
point rotate2(point a, point b, db rad) {point tmp = rotate(a - b, rad); return tmp + b;} // a绕着b逆时针转rad
vct normal(vct A) {return vct(-A.y / len(A), A.x / len(A));}   //单位法向量
bool parallel(vct A, vct B) {return sgn(cross(A, B)) == 0;}
bool cmp2(point a, point b) { // 极角排序 逆时针
    //  1e9 + long double 可以过
    // 建议先用 atan2 / atan2l 对每一个点求出极角实际大小 再比较 作为cmp很慢
    if(sgn(atan2l(a.y, a.x) - atan2l(b.y, b.x)) == 0) return a.x < a.y;
    return atan2l(a.y, a.x) < atan2l(b.y, b.x);
}
// 极角排序
int get_region(point p) {return sgn(p.y) < 0 ? -1 : sgn(p.y) > 0 | (sgn(p.y) == 0 & sgn(p.x) < 0);}
// -1 下半平面 (不包括x轴) 1 上半平面/x轴负半轴 0 原点/x轴正半轴
T dot(point x){ return x.x * x.x + x.y * x.y; }
bool cmp_arg(point a, point b) {
    // 下半平面 < 原点(极角认为是 0) < 正半轴 < 上半平面 < 负半轴
    int p = get_region(a), q = get_region(b);
    if(p != q) return p < q;
    if(a.left(b) == 0) return dot(a) < dot(b); // 共线判线段长度
    return a.left(b) == 1; // 同一区域叉积判断 否则判区间
}
bool cmpy(point A, point B) {return sgn(A.y - B.y) < 0;}
struct cmp_y {bool operator()(const point &a, const point &b) const {return sgn(a.y - b.y) < 0;}};
struct line {
    point p1, p2;
    line() {}
    line(point p1, point p2): p1(p1), p2(p2) {}
    line(point p, db rad) { 
        p1 = p;
		if (sgn(rad - pi / 2) == 0) p2 = (p1 + point(0, 1));
        else p2 = p1 + (point(1, tan(rad)));
    }
    line(T a, T b, T c) {
        if (sgn(a) == 0) p1 = point(0, -c / b), p2 = point(1, -c / b);
        else if (sgn(b) == 0) p1 = point(-c / a, 0), p2 = point(-c / a, 1);
        else p1 = point(0, -c / b), p2 = point(1, (-c - a) / b);
    }
    line(T k, T b) {*this = line(k, -1, b);}
    bool operator < (line a) {
        if(p1.x == p2.x || a.p1.x == a.p2.x) return p1.x != p2.x;
        return (db)(p2.y - p1.y) / (p2.x - p1.x) < (db)(a.p2.y - a.p1.y) / (a.p2.x - a.p1.x);
    } 
    db get_rad() {
        db rad = atan2l(p2.y - p1.y, p2.x - p1.x); // 得到的角度范围是 (-π, π)
        if (rad < 0) rad += 2 * pi; // 如果角度为负,加上 2π 使其变为正值
        return rad;
    }
};
typedef line segment;
int point_line_relation(point p, line v) {return sgn(cross(v.p2 - v.p1, p - v.p1));}   //1在左侧 -1在右侧
// 判断点是否在直线上 可能有精度误差
bool point_on_seg(point p, line v) {return sgn(cross(p - v.p1, v.p2 - v.p1)) == 0 && sgn(dot(p - v.p1, p - v.p2)) <= 0;}
db dis_point_line(point p, line v) {return fabs((db)cross(p - v.p1, v.p2 - v.p1)) / dis(v.p1, v.p2);}
point point_line_proj(point p, line v) {return v.p1 + (v.p2 - v.p1) * (dot(v.p2 - v.p1, p - v.p1) / len2(v.p2 - v.p1));}   //投影
point point_line_symmetry(point p, line v) {point q = point_line_proj(p, v); return point(2 * q.x - p.x, 2 * q.y - p.y);}  //对称点
db dis_point_seg(point p, segment v) {
    if (sgn(dot(p - v.p1, v.p2 - v.p1)) < 0 || sgn(dot(p - v.p2, v.p1 - v.p2)) < 0) return min(dis(p, v.p1), dis(p, v.p2));
	return dis_point_line(p, v);
}
int line_relation(line v1, line v2) {
    if (sgn(cross(v1.p2 - v1.p1, v2.p2 - v2.p1)) == 0) {
        if (point_line_relation(v1.p1, v2) == 0) return -1;//重合
		return 0;//平行
    }
	return 1;//相交
}
point cross_point(line l1, line l2) { //得保证两直线不平行
    auto [x1, y1] = l1;
    auto [x2, y2] = l2;
    point v1 = y1 - x1, v2 = y2 - x2;
    point u = x1 - x2;
    db t = (db)cross(v2, u) / cross(v1, v2);
    return x1 + v1 * t;
}
bool cross_segment(segment l1, segment l2) {
    point a = l1.p1, b = l1.p2, c = l2.p1, d = l2.p2;
    T c1 = cross(b - a, c - a), c2 = cross(b - a, d - a), d1 = cross(d - c, a - c), d2 = cross(d - c, b - c);
    return sgn(c1) * sgn(c2) < 0 && sgn(d1) * sgn(d2) < 0;
}
T polygon_area(vector<point> &p) { //多边形用点集来表示
    int n = p.size();
    T area = 0;
    F(i, 0, n - 1) area += cross(p[i], p[(i + 1) % n]);
    return area;
}
point polygon_center(vector<point> &p) {
    int n = p.size();
    point ans(0, 0);
	if (polygon_area(p) == 0) return ans;
    F(i, 1, n - 1) ans = ans + (p[i] + p[(i + 1) % n]) * cross(p[i], p[(i + 1) % n]);
    return ans / polygon_area(p) / 6;
}
// 内部1 外部0 边界上-1
int point_in_polygon(point p, vector<point> &poly){ 
    // O(n) 算法
    int wn = 0, n = poly.size();
    // wn表示回转数 回转数为0在多边形外部
    // 用光线投射法算回转数 从左边穿过向量+1 从右边穿过向量-1 
    F(i, 0, n - 1) {
        if(point_on_seg(p, line(poly[i], poly[(i + 1) % n]))) return -1;
        int k = sgn(cross(poly[(i + 1) % n] - poly[i], p - poly[i]));
        int d1 = sgn(poly[i].y - p.y);
        int d2 = sgn(poly[(i + 1) % n].y - p.y);
        if(k > 0 && d1 <= 0 && d2 > 0) wn ++;
        if(k < 0 && d2 <= 0 && d1 > 0) wn --;
    }
    if(wn) return 1;
    return 0;
}
// 内部1 外部0 边界上-1
int point_in_polygon2(point a, vector<point> &p) {   
    // O(logn) 凸包本身是按照以一个点为原点极角序排号的 二分后判断是否在对应线段的左侧
    int n = p.size();
    if(n == 1) return a == p[0] ? -1 : 0;
    if(n == 2) point_on_seg(a, line(p[0], p[1])) ? -1 : 0;
    if(a == p[0]) return -1;
    if((p[1] - p[0]).left(a - p[0]) == -1 || (p[n - 1] - p[0]).left(a - p[0]) == 1) return 0; // 判极角序比最小的小或比最大的大
    // 返回第一个cmp为false的 即第一个不在 a - p[0] 右边的点
    auto cmp = [&](const point &u, const point &v) -> bool {return (u - p[0]).left(v - p[0]) == 1;};
    int i = lower_bound(p.begin() + 1, p.end(), a, cmp) - p.begin();
    if(i == 1) return point_on_seg(a, line(p[0], p[1])) ? -1 : 0;
    if(i == n - 1 && point_on_seg(a, line(p[0], p[i]))) return -1;
    int tmp = (p[i] - p[i - 1]).left(a - p[i - 1]);
    return tmp == 0 ? -1 : tmp == 1; 
}
// 凸多边形关于某一方向的极点,复杂度 O(logn)
int extreme(const function<vct(const point&)> &dir, const vector<point>& p) {
    auto check = [&](int i) {return dir(p[i]).left(p[(i+1) % p.size()] - p[i]) >= 0;};
    auto dir0 = dir(p[0]);
    bool check0 = check(0);
    if (!check0 && check(p.size() - 1)) return 0;
    auto cmp = [&](const point &v) {
        int vi = &v - &p[0];
        if (vi == 0) return 1;
        bool checkv = check(vi);
        T t = dir0.left(v - p[0]);
        if (vi == 1 && checkv == check0 && t == 0) return 1;
        return checkv ^ (checkv == check0 && t <= 0);
    };
    return partition_point(p.begin(), p.end(), cmp) - p.begin();
}
// 过凸多边形外一点求凸多边形的切线,返回切点下标,复杂度 O(logn)
// 调用之前 check 是否该点是多边形外的点
// 原理是 标记 a 到 p_i 的直线和 p_{i + 1} 的位置关系,左边标记为L,右边标记为R。切点是两个L和R的分界线。
pair<int, int> tangent(const point &a, const vector<point>& p) {
    // 凸包在line(p[i], a)左侧 在line(p[j], a)右侧 即顺序是p[i] -> p[j]
    int i = extreme([&](const point &u) { return u - a; }, p);
    int j = extreme([&](const point &u) { return a - u; }, p);
    return {i, j};
}
// 求平行于给定直线的凸多边形的切线,返回切点下标,复杂度 O(logn)
pair<int, int> tangent(const line &a, const vector<point>& p) {
    int i = extreme([&](...) { return a.p2 - a.p1; }, p);
    int j = extreme([&](...) { return a.p1 - a.p2; }, p);
    return {i, j};
}
// 闵可夫斯基和
vector<point> minkowski_sum(const vector<point> &p, const vector<point> &q) {
    // 定义边为line
    vector<line> e1(p.size()), e2(q.size()), edge(p.size() + q.size());
    vector<point> res;
    res.reserve(p.size() + q.size());
    auto cmp = [](const line &u, const line &v) {return cmp_arg(u.p2 - u.p1, v.p2 - v.p1);};
    for (int i = 0; i < p.size(); i++) e1[i] = line(p[i], p[(i + 1) % p.size()]);
    for (int i = 0; i < q.size(); i++) e2[i] = line(q[i], q[(i + 1) % q.size()]);
    rotate(e1.begin(), min_element(e1.begin(), e1.end(), cmp), e1.end());
    rotate(e2.begin(), min_element(e2.begin(), e2.end(), cmp), e2.end());
    merge(e1.begin(), e1.end(), e2.begin(), e2.end(), edge.begin(), cmp);
    auto check = [&](const vector<point> &res, const point &u) {
        const auto &back1 = res.back(), &back2 = *prev(res.end(), 2);
        return (back1 - back2).left(u - back1) == 0 && dot(back1 - back2, u - back1) >= -eps;
    };
    auto u = e1[0].p1 + e2[0].p1;
    // 执行闵可夫斯基和的构造
    for (const auto &v : edge) {
        while (res.size() > 1 && check(res, u)) res.pop_back();
        res.push_back(u);
        u = u + (v.p2 - v.p1);
    }
    if (res.size() > 1 && check(res, res[0])) res.pop_back();
    return res;
}

// 动态凸包 支持插入 查询是否在凸包内
struct cmp_Arg {bool operator() (const point &a, const point &b) const {return cmp_arg(a, b);}};
struct dynamic_convex {
    set<point, cmp_Arg> p; //坐标扩大三倍,便于整数运算
    point o; //凸包内一点
    db sum = 0;
    inline auto nxt(decltype(p.begin()) it) const {it++; return it == p.end() ? p.begin() : it; }
    inline auto pre(decltype(p.begin()) it) const {if (it == p.begin()) it = p.end(); return --it; }
    bool is_in(const point &a) const {
        if(p.size() <= 1) return false;
        auto it = p.lower_bound(a * 3 - o);
        if (it == p.end()) it = p.begin();
        return sgn(cross((*it - *pre(it)), ((a * 3 - o) - *pre(it)))) >= 0;
    }
    db func(point a, point b) {
        // 动态维护凸包的信息 这里是周长
        return dis(a, b);
    }
    void add(const point &a) {
        if (p.empty()) { 
            p.insert(a);
            return;
        }
        sum -= func(*p.rbegin(), *p.begin());
        auto it = p.lower_bound(a);
        if (it != p.begin() && it != p.end()) {
            sum -= func(*prev(it), *it);
            sum += func(a, *it);
            sum += func(a, *prev(it));
        } else if (it != p.begin()) {
            --it;
            sum += func(*it, a);
        } else if (it != p.end()) sum += func(*it, a);
        p.insert(a);
        sum += func(*p.begin(), *p.rbegin());
    }
    void del(const point &a) {
        sum -= func(*p.begin(), *p.rbegin());
        auto x = *p.rbegin();
        auto it = p.find(a);
        x = *it;
        if (it != p.begin() && it != p.end() && next(it) != p.end()) {
            sum -= func(*it, *prev(it));
            sum -= func(*it, *next(it));
            sum += func(*prev(it), *next(it));
        } else if (it != p.begin()) sum -= func(*it, *prev(it));
        else if (it != p.end() && next(it) != p.end()) sum -= func(*it, *next(it));
        p.erase(it);
        sum += func(*p.begin(), *p.rbegin());
    }
    void insert(point a) {
        if (p.size() <= 1) {
            add(a * 3);
            return;
        }
        if (p.size() == 2) {
            point u = *p.begin(), v = *p.rbegin();
            o = (u + v + a * 3) / 3;
            p.clear(), sum = 0; // 这里要清零
            add(u - o), add(v - o), add(a * 3 - o);
            return;
        }
        if (is_in(a)) return;
        a = a * 3 - o, add(a);
        auto _it = p.insert(a).first;
        auto it = nxt(_it);
        while (p.size() > 3 && sgn(cross((*it - a), (*nxt(it) - *it))) <= 0) del(*it), it = nxt(_it);
        it = pre(_it);
        while (p.size() > 3 && sgn(cross((*it - *pre(it)), (a - *it))) <= 0) del(*it), it = pre(_it);
    }
    db cal() {return sum / 3.0;}
};
// 平面最近点对
T closest_pair(vector<point> &p) {
    int n = p.size();
    multiset<point, cmp_y> s;
    sort(p.begin(), p.end());
    db res = 1e18;
    for(int i = 0, j = 0; i < n; i ++) {
        while(j < i && dcmp(p[i].x - p[j].x, res) >= 0) s.erase(s.find(p[j ++]));
        for (auto it = s.lower_bound(point(p[i].x, p[i].y - res)); it != s.end() && (*it).y < p[i].y + res; it ++) {
            res = min(res, dis(*it, p[i]));
        } s.insert(p[i]);
    }
    return res;
}
vector<point> convex_hull(vector<point> &p) {
    vector<point> ch;
    sort(p.begin(), p.end());
    p.erase(unique(p.begin(), p.end()), p.end());
    int n = p.size();
    int v = 0;
    F(i, 0, n - 1) {
        while(v >= 2 && sgn(cross(ch[v - 1] - ch[v - 2], p[i] - ch[v - 1])) <= 0) v --, ch.pop_back();
        v ++, ch.push_back(p[i]);
    } int j = v;
    Fd(i, n - 2, 0) {
        while(v > j && sgn(cross(ch[v - 1] - ch[v - 2], p[i] - ch[v - 1])) <= 0) v --, ch.pop_back();
        v ++, ch.push_back(p[i]);
    } 
    if(n > 1) ch.pop_back();
    return ch;
}
T rotating_calipers(vector<point> &ch) { //旋转卡壳求凸包直径
    // 点到极边具有单调性
    int n = ch.size();
    if(n == 2) return dis(ch[0], ch[1]);
    // if(n == 2) return len2(ch[0] - ch[1]); // 求距离的平方
    db res = 0; int j = 0;
    F(i, 0, n - 1) {
        point u = ch[i], v = ch[(i + 1) % n];
        while(sgn(cross(u - ch[j], v - ch[j]) - cross(u - ch[(j + 1) % n], v - ch[(j + 1) % n])) <= 0)
            j = (j + 1) % n;
        // 有向面积 一定为正
        res = max({res, dis(ch[j], ch[i]), dis(ch[j], ch[(i + 1) % n])});
        // res = max({res, len2(ch[j] - ch[i]), len2(ch[j] - ch[(i + 1) % n])});
    }
    return res;
}
struct circle{
    point c;
    T r;
    circle() {}
    circle(point c, T r) : c(c), r(r) {}
    circle(T x, T y, T _r) {c = point(x, y); r = _r;}
    point get_point(T a){//通过圆心角求坐标
        return point(c.x + cosl(a)*r, c.y + sinl(a)*r);
    }
};
int point_circle_relation(point p, circle C) {
    db dst = dis(p, C.c);
    if(sgn(dst - C.r) < 0) return 0;
    if(sgn(dst - C.r) == 0) return 1;
    return 2; // 外部
}
int line_circle_relation(line v, circle C) {
    db dst = dis_point_line(C.c, v);
    if(sgn(dst - C.r) < 0) return 0;
    if(sgn(dst - C.r) == 0) return 1;
    return 2;
}
int seg_circle_relation(segment v, circle C) {
    db dst = dis_point_seg(C.c, v);
    if(sgn(dst - C.r) < 0) return 0;
    if(sgn(dst - C.r) == 0) return 1; 
    return 2;
}
int line_cross_circle(line v, circle C, point &pa, point &pb) {
    // 圆和直线相交的两个点 返回值是交点个数
    if(line_circle_relation(v, C) == 2) return 0;
    point q = point_line_proj(C.c, v);
    db d = dis_point_line(C.c, v);
    db k = sqrt(C.r * C.r - d * d);
    if(sgn(k) == 0) {pa = q, pb = q; return 1;}
    point nn = (v.p2 - v.p1) / len(v.p2 - v.p1);
    pa = q + nn * k, pb = q - nn * k;
    return 2;
}
db circle_overlap_area(point c1, db r1, point c2, db r2){
    // 两个圆的覆盖面积
    db d = len(c1 - c2);
    if(r1 + r2 < d + eps) return 0.0;
    if(d < fabs(r1 - r2) + eps){
        db r = min(r1, r2);
        return pi * r * r;
    }
    db x = (d * d + r1 * r1 - r2 * r2) / (2.0 * d);
    db p = (r1 + r2 + d) / 2.0;
    db t1 = acosl(x / r1);
    db t2 = acosl((d - x) / r2);
    db s1 = r1 * r1 * t1;
    db s2 = r2 * r2 * t2;
    db s3 = 2 * sqrt(p * (p - r1) * (p - r2) * (p - d));
    return s1 + s2 - s3;
}
point circle_center(point a, point b, point c) {
    // 三点确定的圆中心
    db a1 = b.x - a.x, b1 = b.y - a.y, c1 = (a1 * a1 + b1 * b1) / 2;
    db a2 = c.x - a.x, b2 = c.y - a.y, c2 = (a2 * a2 + b2 * b2) / 2;
    db d = a1 * b2 - a2 * b1;
    return point(a.x + (c1 * b2 - c2 * b1) / d, a.y + (a1 * c2 - a2 * c1) / d);
}
// 最小圆覆盖
void min_cover_circle(vector<point> &p, point &c, T &r) {
    int n = p.size();
    random_shuffle(p.begin(), p.end());
    c = p[0], r = 0;
    F(i, 1, n - 1) if(point_circle_relation(p[i], circle(c, r)) == 2) {
        c = p[i], r = 0;
        F(j, 0, i - 1) if(sgn(dis(p[j], c) - r) > 0) {
            c = (p[i] + p[j]) / 2;
            r = dis(p[j], c);
            F(k, 0, j - 1) if(sgn(dis(p[k], c) - r) > 0) {
                c = circle_center(p[i], p[j], p[k]);
                r = dis(p[i], c);
            }
        }
    }
}

const int N = 305;
vector<point> a, b;
vector<int> ed[N];
pii E[N << 1];
int now = 0, vst[N << 1];
bool cmp(int x, int y) {return cmp_arg(a[x] - a[now], a[y] - a[now]);}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m, c; cin >> n >> m >> c;
    map<pii, int> rk;
    F(i, 0, n - 1) {
        int x, y; cin >> x >> y;
        a.push_back(point(x, y));   
    }
    F(i, 0, m - 1) {
        int x, y; cin >> x >> y;
        b.push_back(point(x, y));
    }
    F(i, 0, c - 1){
        int u, v; cin >> u >> v;
        u --, v --;
        ed[u].push_back(v), ed[v].push_back(u);
        E[2 * i] = {u, v}, E[2 * i + 1] = {v, u};
        rk[{u, v}] = 2 * i, rk[{v, u}] = 2 * i + 1;
    }
    F(i, 0, n - 1) {
        now = i;
        sort(ed[i].begin(), ed[i].end(), cmp);
    }
    vector<vector<point>> polygon;
    vector<vector<int>> Polygon;
    vector<int> area;
    F(i, 0, 2 * c - 1) if(! vst[i]) {   
        int tmp = i;
        vector<point> p;
        vector<int> q; 
        p.push_back(a[E[tmp].fi]);
        q.push_back(E[tmp].fi);
        while(! vst[tmp]) {
            vst[tmp] = 1;
            auto [u, v] = E[tmp];
            p.push_back(a[v]);
            q.push_back(v);
            int f = -1;
            for(int j = 0; j < ed[v].size(); j ++) if(ed[v][j] == u) {
                f = j; break;   
            }
            assert(f != -1);
            int nxt = ed[v][(f + ed[v].size() - 1) % ed[v].size()];
            tmp = rk[{v, nxt}]; 
        }
        ll sum = polygon_area(p);
        polygon.push_back(p), area.push_back(sum), Polygon.push_back(q);
    } 
    auto get_area = [&](point p) -> int {
        int qsy = -1;
        for(int i = 0; i < polygon.size(); i ++) if(area[i] > 0 && (qsy == -1 || area[i] < area[qsy])) {
            if(point_in_polygon(p, polygon[i]) == 1) qsy = i; 
        } // 最近的一层包含这个点的是哪个 qaq表示是否额外存在一个多边形使得该点在多边形边界上
        return qsy;
    };
    vector<int> res(c);
    auto nanani = [&](int id) -> void {
        if(id == -1) return;
        int sz = Polygon[id].size();
        for(int i = 0; i < sz; i ++) {
            int u = Polygon[id][i], v = Polygon[id][(i + 1) % sz];
            res[rk[{u, v}] / 2] = 1; 
        } 
    };
    int P = area.size();
    vector<int> flag(P);
    F(i, 0, P - 1) if(area[i] <= 0) {
        flag[i] = get_area(polygon[i][0]);
    }
    for(auto o : b) {
        int f = get_area(o);
        nanani(f);
        for(int i = 0; i < P; i ++) if(area[i] <= 0 && flag[i] == f) nanani(i);
    }
    for(auto x : res) cout << x; cout << "\n";
    return 0;
}
//sldl

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3712kb

input:

4 1 3
-2 0
0 2
2 0
0 1
0 3
1 2
2 3
1 3

output:

111

result:

ok single line: '111'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3620kb

input:

13 35 13
13 12
16 -3
18 4
4 -7
23 -22
9 -23
23 11
12 -1
19 -5
15 -15
5 -15
-17 11
-17 -13
-20 19
11 -12
-10 14
-3 14
7 -4
-10 -23
-19 -12
-13 1
-22 10
-21 -1
18 -9
-8 1
13 22
12 -23
-9 -9
-12 -20
4 -3
-6 17
14 -10
10 13
-5 -2
-4 -12
13 22
-18 -21
19 5
12 -18
4 0
3 -17
5 -2
-2 0
8 0
-8 1
14 -18
3 -9
...

output:

1111111111111

result:

ok single line: '1111111111111'

Test #3:

score: -100
Wrong Answer
time: 1ms
memory: 3828kb

input:

68 59 168
51 -57
-26 -51
-31 58
-45 -78
-46 -49
-53 14
76 -69
-64 32
58 -49
-1 12
-65 28
-15 -10
29 -53
25 -32
78 -41
24 -37
69 56
54 -10
3 36
-18 46
53 -30
41 -2
-30 13
-58 -37
-20 42
-48 -38
-42 22
64 0
9 -56
7 -11
-66 -23
19 -9
-26 -6
-61 -68
57 13
-13 50
-15 -11
-77 47
-77 57
78 51
-37 56
-75 24...

output:

111111111111111111100001011000001001110111110111101011011001111110011011101111110111011101001000000001010100111111100110000100110100101101111111110011001111111100100011

result:

wrong answer 1st lines differ - expected: '011111111111111111100001011000...1111111110011001111111100100011', found: '111111111111111111100001011000...1111111110011001111111100100011'