QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#673272	#7511. Planar Graph	Nanani	AC ✓	1ms	3912kb	C++17	20.9kb	2024-10-24 21:30:01	2024-10-24 21:30:02

Judging History

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

[2024-10-24 21:30:02]
评测

测评结果：AC
用时：1ms
内存：3912kb

查看

[2024-10-24 21:30:01]
提交

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;
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 = 1005;
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);
    } 
    // for(auto qaq : Polygon) {
    //     cout << ":\n";
    //     for(auto x : qaq) cout << x + 1 << " ";
    //     cout << "\n";
    // }
    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
/*
4 1 4

7 1
8 10
4 4
2 4

2 6

1 3
1 4
2 4
1 2

*/

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 3672kb

input:

output:

result:

ok single line: '111'

Test #2:

score: 0

Accepted

time: 0ms

memory: 3632kb

input:

output:

1111111111111

result:

ok single line: '1111111111111'

Test #3:

score: 0

Accepted

time: 1ms

memory: 3660kb

input:

output:

011111111111111111100001011000001001110111110111101011011001111110011011101111110111011101001000000001010100111111100110000100110100101101111111110011001111111100100011

result:

ok single line: '011111111111111111100001011000...1111111110011001111111100100011'

Test #4:

score: 0

Accepted

time: 0ms

memory: 3676kb

input:

output:

00000000000000000000000000000000000000000000000000000000000001000000000000000000000000000001000000000000000000000000000000000000000000000000001000000000000000

result:

ok single line: '000000000000000000000000000000...0000000000000001000000000000000'

Test #5:

score: 0

Accepted

time: 0ms

memory: 3912kb

input:

output:

10010010000101001010010100101100100000001010001000000001101111101000011111000000001011000100000010100000000100011011000000110

result:

ok single line: '100100100001010010100101001011...0010100000000100011011000000110'

Test #6:

score: 0

Accepted

time: 1ms

memory: 3672kb

input:

output:

000110010001001101100010110101100100011110011110110101010100110011111010101110101001001011100000110101000100010011100100100110100001011010001010001010000100011000001101010110011001101111010000011001000011

result:

ok single line: '000110010001001101100010110101...0011001101111010000011001000011'

Test #7:

score: 0

Accepted

time: 1ms

memory: 3724kb

input:

59 96 152
-75886847 147807525
335545968 317138952
262969730 -308175740
91308409 -162085508
-397786268 -191693417
-227565597 195627938
45666011 253210394
-311142459 58197832
-412164189 -270215767
-12639523 -314154358
-269901472 -366179516
-306681757 -167771007
194329800 -339296479
-12501616 -15788817...

output:

01110111111111111110101110111011101111110011100110100111110110001110111101100111100111010111111110110101110111110011111001110001111100010111110111111111

result:

ok single line: '011101111111111111101011101110...1110001111100010111110111111111'

Test #8:

score: 0

Accepted

time: 0ms

memory: 3840kb

input:

output:

000010000000000110001101000110000000010010000001001001100000010010000010001100010011010101001000010

result:

ok single line: '000010000000000110001101000110...0010001100010011010101001000010'

Test #9:

score: 0

Accepted

time: 0ms

memory: 3672kb

input:

63 1 175
50549954 -224104196
-187903718 57327090
-61398050 89271831
72686467 -167765054
4226095 73332567
-80682032 -158732552
-366425325 -180661648
-210787891 -107411752
44235201 233049038
-29484914 -280845598
228925315 -106736012
-169221325 64453690
-127160591 78410226
374001485 -312357450
31528300...

output:

0000000100000000000000000000000000010000000000000000000001000000000000000010000000000000000000000000000000000010000000000000010000000000000001000000000100000101000000000001000

result:

ok single line: '000000010000000000000000000000...0000000100000101000000000001000'

Test #10:

score: 0

Accepted

time: 0ms

memory: 3692kb

input:

82 4 66
182782804 77923360
117828203 139218692
-110620000 89777361
273011388 138341008
294610527 -194481138
294204618 -290402347
194417551 48839146
-161919200 -261350494
-260772975 -239789170
117370125 245536520
-201599590 -82451402
291486591 84106590
296266013 309943147
-220542664 54399074
24021444...

output:

111101011111111111111111010111111101010111100110100011111111011111

result:

ok single line: '111101011111111111111111010111...1010111100110100011111111011111'

Test #11:

score: 0

Accepted

time: 1ms

memory: 3668kb

input:

65 50 147
-581452360 190355182
-642896619 -572084384
-305018177 -539060586
-328404608 -74526018
198824769 -402666976
-604806291 420433161
646918331 -591294299
360443372 -456307852
253325248 -341024549
-656241212 302363402
524405246 -499973260
-531933602 617077471
-185233072 -318131117
-362315669 -49...

output:

011111111110100110100010010101111011110111010001101101001001111101111111011011011001001001101100100111110111001101101010100100110111100110101010100

result:

ok single line: '011111111110100110100010010101...1010100100110111100110101010100'

Test #12:

score: 0

Accepted

time: 0ms

memory: 3648kb

input:

output:

1000000100000100000000001001000000000010101000000100000011001000000000000001000000000000000000000000000000000000000010011000000000000000000010

result:

ok single line: '100000010000010000000000100100...0000010011000000000000000000010'

Test #13:

score: 0

Accepted

time: 1ms

memory: 3740kb

input:

88 68 244
452074073 749836590
-422267242 -370342423
-649645359 303851355
285738514 -585228292
674035872 344344527
-564943027 45741258
301794983 564572022
349063999 218051130
668851769 598897930
596201080 -750109936
95583385 363387733
130300372 -350613210
-126422550 -684185703
-117024972 -406661982
-...

output:

1111011101010010110011001011101101100000000010100110001111000010001011100110001100101100000010001011101100010000010110111000010101010100101011011101011010011110000111010000011110110111101110011111001111101000110001000110101101001101111100111101

result:

ok single line: '111101110101001011001100101110...1000110101101001101111100111101'

Test #14:

score: 0

Accepted

time: 0ms

memory: 3828kb

input:

24 47 58
-536382548 -36211682
-617682678 630246425
-680303961 -753887401
-576626558 -547501154
-166237320 -247093489
-780629487 -564369462
745821462 -462233962
-29960131 -120134355
-215230222 568441689
-505349805 471834374
-268168811 -773902784
-436226654 -153342090
-686102938 -414449668
-318346027 ...

output:

1011111110101111101111111011101111100110100110101011111011

result:

ok single line: '1011111110101111101111111011101111100110100110101011111011'

Test #15:

score: 0

Accepted

time: 1ms

memory: 3888kb

input:

76 82 181
-835091273 636197461
-809826661 -915012307
-514114180 762992620
-801978217 -646901746
-937647819 -73101245
632623370 -798225996
-949969476 -45929520
677089833 -491546441
-818746494 -457407341
-23609804 -63980274
927682282 -371416961
-936340868 -741789992
-82906350 -740214368
-884276937 -32...

output:

1011111111110100011011111001011110100011001111111001011100111111111110011100101011101011101011111011001100001001110001101110010010101111000101010100111100011011110001100110110110011

result:

ok single line: '101111111111010001101111100101...1100011011110001100110110110011'

Test #16:

score: 0

Accepted

time: 0ms

memory: 3680kb

input:

output:

110111101111111110111011111111111111111

result:

ok single line: '110111101111111110111011111111111111111'

Test #17:

score: 0

Accepted

time: 0ms

memory: 3648kb

input:

53 1 95
249310291 444009281
-51319591 -127058272
-521364452 184610945
-21697253 -380031119
-765296404 788815734
480089046 -792178676
285516793 131912022
715950950 -65482217
36211136 -559456984
-46323546 622669323
812068024 -71601366
-6695845 -158750172
23940379 638024824
-792521738 -179875992
-72088...

output:

00000000000010000100000000000100000000000000000000000000000000000000000100000000000000000000000

result:

ok single line: '000000000000100001000000000001...0000000100000000000000000000000'

Test #18:

score: 0

Accepted

time: 0ms

memory: 3756kb

input:

output:

1111111111111111111111111111110111111111111111111111111111111111111

result:

ok single line: '111111111111111111111111111111...1111111111111111111111111111111'

Test #19:

score: 0

Accepted

time: 0ms

memory: 3824kb

input:

27 42 12
-196639452 -910071469
556979079 -24132720
-907504137 -798429714
217201737 894945050
592735402 -891961813
351726786 -961077191
428253659 -337157490
-814353097 482187973
-746163779 14512669
-639377173 -925754520
-499592664 319782459
-500528351 591167527
-701230268 -495398846
-836405665 445706...

output:

111111111111

result:

ok single line: '111111111111'

Test #20:

score: 0

Accepted

time: 1ms

memory: 3644kb

input:

output:

011111100111111110111110011111010010001111111101100111011111111011110101110101011001111111011111111010

result:

ok single line: '011111100111111110111110011111...1110101011001111111011111111010'

Test #21:

score: 0

Accepted

time: 1ms

memory: 3756kb

input:

81 70 214
501181684 467604004
467393962 79858372
-24971604 -76855555
310835183 -451578432
529058882 -371153027
10117013 439009502
-102203223 498873755
104983339 -167287519
-234656041 548196249
-355162848 -403411047
-303715296 -31203991
412378489 -143945211
-38540379 -474967805
-321224760 115499601
-...

output:

0010100000110011101001110011111111000011110110011000110000111111000110011111000001000100111000101111110111101011101110100000001101010100110100011011111111000100110110010100010001101111000101110110010110011010110000

result:

ok single line: '001010000011001110100111001111...1000101110110010110011010110000'

Test #22:

score: 0

Accepted

time: 0ms

memory: 3612kb

input:

2 1 0
-381381789 -155480688
476986136 269997025
374524257 360034879

output:

result:

ok 0 lines

Test #23:

score: 0

Accepted

time: 1ms

memory: 3860kb

input:

64 98 165
368476226 -245975441
321964920 84032145
168655443 132633922
191654925 58795031
174065240 -211635910
349833228 30545690
200179574 272085215
100336543 -391757623
172093450 34273303
-393548578 392781830
-335701529 189217228
-23681938 -213109493
-337162597 334472127
-11931889 167942850
9961263...

output:

111111010111111101101110011011111111011001110111111001000111110111111011110011010101111101101111101101101111011111111101100001010011101101100111100111011100111101100

result:

ok single line: '111111010111111101101110011011...1101100111100111011100111101100'

Test #24:

score: 0

Accepted

time: 0ms

memory: 3644kb

input:

48 3 106
-11919288 401311957
-300306784 -473247000
-572232580 -129053552
-253134521 21856503
-435640199 -269285358
28497548 154734438
449368223 254505621
-41113963 -73600818
-445437245 -234603342
-434722859 -577811918
-411116809 140213809
188703595 -442513896
-200064854 -383148625
-278682300 2351034...

output:

0000000000001000000100000010100000110110000000000010010000010000001000000000000010100000100000000000100000

result:

ok single line: '000000000000100000010000001010...0000010100000100000000000100000'

Test #25:

score: 0

Accepted

time: 1ms

memory: 3764kb

input:

output:

11011111111010110111111111111100101111111111011011011111111111111111

result:

ok single line: '110111111110101101111111111111...1111111011011011111111111111111'

Test #26:

score: 0

Accepted

time: 0ms

memory: 3696kb

input:

40 1 72
-3372678 23575085
-14527803 -22685257
-5770297 10287106
15480880 -9727089
-13598905 -11137818
-23830038 -22435224
-16870142 11247699
22240990 -4980969
19912096 1617242
8897796 -1011804
20884847 -13905376
1075116 -18515777
-24742774 -21603292
-17315892 17920458
3074471 2211097
-19379610 -1295...

output:

000000000001000000000000000000000010001000001000000000000000000000000000

result:

ok single line: '000000000001000000000000000000...0001000000000000000000000000000'

Test #27:

score: 0

Accepted

time: 1ms

memory: 3860kb

input:

100 1 161
-80137690 25887305
-112675497 -60746940
113490133 75503508
61659499 44746640
-14968017 -100091877
-104246751 105396818
84695481 27512974
26707762 30557205
-50252976 43123976
-87452977 -114609404
-90960888 -29046502
56406267 47388462
31699712 -101291314
-68208465 -106761143
-67054841 -66583...

output:

00001000000001000000000000000000100000000000000001000100110000010001000000001000100110100000010000010000001000000101000101000000100001010000001000000001010000100

result:

ok single line: '000010000000010000000000000000...0001010000001000000001010000100'

Test #28:

score: 0

Accepted

time: 0ms

memory: 3688kb

input:

output:

00000100001000000000000000000000000000000000110

result:

ok single line: '00000100001000000000000000000000000000000000110'

Test #29:

score: 0

Accepted

time: 0ms

memory: 3904kb

input:

62 1 97
-288124496 55427633
-106217896 -320441624
412921225 229817207
-275224721 -519311403
325626455 17792730
694140 -370700355
221344845 -292576453
278441135 91382191
-264581148 605253608
288040649 -257804861
565015276 321207185
-376426170 -97185967
-275609526 177082714
165378518 509619762
-289226...

output:

0000011010101001100001000001010001010000000000010010000011100000000110000101010000010001000000100

result:

ok single line: '000001101010100110000100000101...0110000101010000010001000000100'

Test #30:

score: 0

Accepted

time: 1ms

memory: 3640kb

input:

output:

111111110010111111111100100111001111101111101111110100110010011111111101001101101011100111111111010111

result:

ok single line: '111111110010111111111100100111...1001101101011100111111111010111'

Test #31:

score: 0

Accepted

time: 0ms

memory: 3704kb

input:

38 1 88
-446400801 -432601444
199781326 451912811
-310982031 -352396254
-371451563 446705858
-455182293 -115870523
192342741 -247378438
52021139 -157133935
425618795 81760805
-289321740 73826020
237967642 245405012
139542786 408639766
-383554281 -393726138
-242304554 230654135
180115969 -217593842
-...

output:

0000001000000000000001000000000000000000000000000000000001000000000000000000000000000000

result:

ok single line: '000000100000000000000100000000...1000000000000000000000000000000'

Test #32:

score: 0

Accepted

time: 1ms

memory: 3808kb

input:

76 1 203
-114230262 198639426
-233519874 304535156
71925374 17384831
61187577 -239527087
-1301445 -284823715
-17528795 -87694527
-71891668 -87551507
297990011 72199440
298333978 -166850097
-217459867 241758763
182666664 130453342
-45491109 -127986422
-66978149 -250733511
302411526 -274384662
1224861...

output:

00000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000001000000000000000

result:

ok single line: '000000000000000010000000000000...0100000000000001000000000000000'

Test #33:

score: 0

Accepted

time: 0ms

memory: 3680kb

input:

output:

111111111111111

result:

ok single line: '111111111111111'

Test #34:

score: 0

Accepted

time: 0ms

memory: 3692kb

input:

69 1 60
59116022 108407
94778844 -122980783
41883194 19636800
-187451713 6187507
-20192750 220459924
-20310470 -194332991
60290065 186874427
117664759 -156393226
5968406 70428711
85377868 168601959
-121623776 -10805246
-142624509 79757169
35682197 -40150966
143098357 -84077220
201596816 128462146
-1...

output:

110000000011000000000010000000000010000000000000000000000000

result:

ok single line: '110000000011000000000010000000000010000000000000000000000000'

Test #35:

score: 0

Accepted

time: 0ms

memory: 3704kb

input:

50 80 107
-136821224 438342159
-418706353 9399993
227086984 708880509
-699325397 650928735
-683886486 -542763048
445537952 437994317
-547883573 -612772235
674767503 301331010
711167575 -504002762
-302413612 585767673
-617012243 -579675418
436969684 -389018306
-176369404 -556177193
199740497 -1279731...

output:

11101001110110011111011110101111111101110111111101011111011011001110111110101110111110110110010101111111111

result:

ok single line: '111010011101100111110111101011...1110111110110110010101111111111'

Test #36:

score: 0

Accepted

time: 0ms

memory: 3688kb

input:

27 1 64
-25051747 96640487
11315454 -51389072
95068722 16273286
-22843851 -70513190
-74137758 -9111615
21053920 -107867712
-32614318 103549910
2393150 19168515
-90542955 -54660103
-13312789 63595983
-8635454 74271767
100997992 7975546
42195819 121435672
-33155278 68709317
-6510510 -64937636
55899006...

output:

0000000000001000000000000000010000000100000100001000000000010100

result:

ok single line: '0000000000001000000000000000010000000100000100001000000000010100'

Test #37:

score: 0

Accepted

time: 0ms

memory: 3624kb

input:

23 1 18
-587851478 132420486
-475758602 -400608037
-98931454 -551980136
-340511412 -276505996
-83836150 55454149
-54179724 206559858
-455797934 -154251228
464412902 39052879
301564372 -401006721
-546638191 425633896
-186653938 573749346
134221719 588337034
-70138896 -525202115
-327528605 540665503
2...

output:

011011111111111110

result:

ok single line: '011011111111111110'

Test #38:

score: 0

Accepted

time: 0ms

memory: 3684kb

input:

52 38 52
-172741511 530619780
549977080 474404309
-547915702 438421321
-391365339 34163364
548153306 -519024791
-180235574 347572036
-163100589 273868723
-425058097 56352201
-43670197 -199317783
183157655 -212775074
248267302 322744067
147359299 445994893
-44259658 -345348250
27220688 248380193
4262...

output:

1111111111111111111111111111111111111111111111111111

result:

ok single line: '1111111111111111111111111111111111111111111111111111'

Test #39:

score: 0

Accepted

time: 1ms

memory: 3868kb

input:

output:

00000000001000001001000000000010000000000001001000000000010001000000001001000000010000000000000000000000001100000000010010000000000000000000000000000000000000000000000000000000000000100000

result:

ok single line: '000000000010000010010000000000...0000000000000000000000000100000'

Test #40:

score: 0

Accepted

time: 0ms

memory: 3704kb

input:

100 1 151
113561380 110916055
-202042971 210205642
12303413 111952262
28581056 84194411
205637761 181102235
156312466 137951229
118778185 -93636318
-119495509 -134216633
206600413 166496494
196542187 199300725
-224152338 86716607
28676325 -214678702
-73145624 -46988839
-118078074 138104323
-28028396...

output:

0000000100000000000001000000000010000000000000000001000000000000000100000000001000000000000000000000000000000000000000101000000000000000000000000000000

result:

ok single line: '000000010000000000000100000000...1000000000000000000000000000000'

Test #41:

score: 0

Accepted

time: 0ms

memory: 3628kb

input:

12 84 12
-36439905 31935320
-68591283 13528537
-36821752 -10120895
-23268663 -51987362
-17270332 27599642
-14220756 66133940
4217801 -58637875
20311027 52760847
-672927 -20784000
-42946290 64478308
45462745 -2041480
-32664304 -62771948
69287632 -42291606
12112366 24444326
17494701 -24483473
29503643...

output:

111111111111

result:

ok single line: '111111111111'

Test #42:

score: 0

Accepted

time: 0ms

memory: 3624kb

input:

output:

111111111111111111111111111111111111111111

result:

ok single line: '111111111111111111111111111111111111111111'

Test #43:

score: 0

Accepted

time: 0ms

memory: 3608kb

input:

13 1 11
50001509 48881161
-59857365 30669626
54162135 62601120
-12056654 -29581450
20555084 -37862653
-64440885 65834270
41954171 -10072075
-10372539 -12139482
-61460535 -47231591
-14493051 -29020806
-48650146 45492863
18452711 14049436
39478906 -44669995
-59830633 -32027973
6 12
3 13
12 13
5 12
10 ...

output:

11101110111

result:

ok single line: '11101110111'

Test #44:

score: 0

Accepted

time: 0ms

memory: 3648kb

input:

78 1 121
396995327 158214181
415024439 -659811167
448527806 154062383
208165138 -391842000
193474414 -134150962
-323390941 -175627012
-731206356 -703653906
328435642 42666595
448320717 -192428896
-179674960 -193976132
150468115 -152990895
-169233627 -649281727
-329098117 691631973
-733457437 -610681...

output:

0010000000000000000001000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000

result:

ok single line: '001000000000000000000100000000...0000000000000000000000000000000'

Test #45:

score: 0

Accepted

time: 0ms

memory: 3824kb

input:

output:

111111010111111111110111011111111111101111110110111

result:

ok single line: '111111010111111111110111011111111111101111110110111'

Test #46:

score: 0

Accepted

time: 0ms

memory: 3640kb

input:

output:

111111111111111111111111111111111001111111011

result:

ok single line: '111111111111111111111111111111111001111111011'

Test #47:

score: 0

Accepted

time: 1ms

memory: 3780kb

input:

99 46 123
-592182435 -645809554
92283434 -714819045
-423525473 -164302428
475848582 -412025661
-536332323 697460306
198041990 258905077
283984406 127967289
-617604502 582772298
-699941320 -230163014
-710474304 -222084831
394078090 -730012818
-477075045 77739018
325949099 -371309760
572486929 -338912...

output:

111111101111110111111110101111110111111110111111111010011110111011110111111110111111011101011100111111111100100000111110111

result:

ok single line: '111111101111110111111110101111...1100111111111100100000111110111'

Test #48:

score: 0

Accepted

time: 1ms

memory: 3712kb

input:

output:

111000011000010011011000111000001110101011100011100111000000100111101100010010000010000000000000100100000001011010001110011010101101001001010001000010100101011000001100000100011101100101000111011110000011010111000000000010000010011000001010000001000110001001101100001101

result:

ok single line: '111000011000010011011000111000...0000001000110001001101100001101'

Test #49:

score: 0

Accepted

time: 0ms

memory: 3672kb

input:

51 1 31
-92370944 -764113248
692325784 -851433764
-96851584 824901875
390848076 761934344
-413030187 -898297145
-171510577 841381560
233016216 422104783
721487331 -481096520
871381319 -715381491
-172785176 -411474589
694130790 -210954359
198576848 -682804186
759565175 -146802975
-505077293 -41499702...

output:

1111111111111111111111111111111

result:

ok single line: '1111111111111111111111111111111'

Test #50:

score: 0

Accepted

time: 0ms

memory: 3804kb

input:

32 95 1
245177609 199504310
90689086 -175898276
179952610 -177411595
10121423 -177583648
-62422073 -9211145
-157720737 -177578288
-37542857 224562278
30116853 81612384
-184921179 234707204
123542122 8971776
-164051213 -68266830
144538639 -50285622
704052 -51042388
-92307305 -92629769
132984052 -2274...

output:

result:

ok single line: '1'