HDU 6762 Mow (2020 Multi-University Training Contest 1 1012）半平面交

Mow

分析

将多边形的边向内部缩 r 个单位长度，然后这些边所围成的内部区域，就是圆心的合法范围，该范围也是一个多边形，假设面积是\(a\)，周长是\(b\)，那么可以知道圆可以覆盖的面积是 \(a + b * r + \pi *r^2\)。现在问题转换为了求这些边所围成的区域，这正是半平面交所要做的事情。

需要用到的知识点：

极角排序
直线平移
直线求交点
单调队列求半平面交
多边形利用三角剖分求面积，求周长

另外需要注意的是该题目精度有些卡，需要用longdouble，另外要注意一些常用函数后面加 l,比如acos要换成acosl，sqrt要换成sqrtl等。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int inf = 0x3f3f3f3f;

#define dbg(x...) do { cout << "\033[32;1m" << #x <<" -> "; err(x); } while (0)

void err() { cout << "\033[39;0m" << endl; }

template<class T, class... Ts> void err(const T& arg,const Ts&... args) { cout << arg << " "; err(args...); }

const int N = 200 + 5;

typedef long double db;

const db eps = 1e-12;

const db pi = acosl(-1.0);

int T, n;

db A, B, r;

int sgn(db x){

    if(fabs(x) < eps) return 0;

    if(x < 0) return -1;

    return 1;

}

inline db sqr(db x){return x * x;}

struct Point{

    db x, y;

    Point(){}

    Point(db x, db y):x(x), y(y){}

    void input(){

        cin >> x >> y;

    }

    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(y - b.y) < 0 : x < b.x;

    }

    // 向量运算

    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);

    }

    db operator ^ (const Point &b) const{

        return x * b.y - y * b.x;

    }

    db operator * (const Point &b) const{

        return x * b.x + y * b.y;

    }

    // 标量运算 * /

    Point operator *(const db &k) const{

        return Point(x * k , y * k);

    }

    Point operator / (const db &k) const{

        return Point(x / k, y / k);

    }

    db len(){

        return sqrtl(x * x + y * y);

    }

    db len2(){

        return x * x + y * y;

    }

    db distance(Point p) {

        return (*this - p).len();

    }

    Point trunc(db r) {

        db l = len();

        if(sgn(l) == 0) return *this;

        return Point(x * r / l, y * r / l);

    }

    Point rotleft(){

        return Point(-y, x);

    }

    Point rotright(){

        return Point(y, -x);

    }

}p[N];

struct Line{

    Point s, e;

    Line(){}

    Line(Point s, Point e) : s(s), e(e){}

    void input(){

        s.input();e.input();

    }

    bool operator == (Line v){

        return (s == v.s) && (e == v.e);

    }

    db length() {

        return s.distance(e);

    }

    bool parallel(Line v){

        return sgn((e - s) ^ (v.e - v.s)) == 0;

    }

    Point crossPoint(Line v) {

        db a1 = (v.e - v.s) ^ (s - v.s);

        db a2 = (v.e - v.s) ^ (e - v.s);

        db t = a2 - a1;

        return Point((s.x * a2 - e.x * a1) / t, (s.y * a2 - e.y * a1) / t);

    }

}l[N];

struct Polygon{

    int n;

    Point p[N];

    Line l[N];

    void input(int n) {

        this->n = n;

        for(int i=0;i<n;i++) p[i].input();

    }

    db getCircumference(){

        db res = 0;

        for(int i=0;i<n;i++) res += p[i].distance(p[(i+1)%n]);

        return res;

    }

    db getArea(){

        db res = 0;

        for(int i=0;i<n;i++)res += (p[i] ^ p[(i+1)%n]);

        return fabs(res) / 2;

    }

    struct cmp{

        Point p;

        cmp(const Point &p0) {p = p0;}

        bool operator()(const Point &aa, const Point &bb) {

            Point a = aa, b = bb;

            int d = sgn((a - p) ^ (b - p));

            if(d == 0) return sgn(a.distance(p) - b.distance(p)) < 0;

            return d > 0;

        }

    };

    void norm(){

        Point mi = p[0]; for(int i=1;i<n;i++) mi = min(mi, p[i]);

        sort(p, p+n, cmp(mi));

    }

}lawn, poly;

void adjust(){

    lawn.norm();

    for(int i=0;i<n;i++){

        Point a = lawn.p[i], b = lawn.p[(i+1)%n];

        Point aa = a + (b - a).rotleft().trunc(r);

        Point bb = b + (b - a).rotleft().trunc(r);

        l[i] = Line(aa, bb);

    }

}

bool getHalfPlanes(){

    Line q[N];

    Point t[N];

    int ll = 1, rr = 0;

    for(int i=0;i<n;i++){

        if(l[i] == l[(i-1+n)%n] || l[i].parallel(l[(i-1+n)%n]))continue;

        while(ll < rr && ((l[i].e - t[rr]) ^ (l[i].s - t[rr])) > eps) rr--;

        while(ll < rr && ((l[i].e - t[ll+1]) ^ (l[i].s - t[ll+1])) > eps) ll++;

        q[++rr] = l[i];

        if(ll < rr) t[rr] = q[rr].crossPoint(q[rr-1]);

    }

    while(ll < rr && ((q[ll].e - t[rr]) ^ (q[ll].s - t[rr])) > eps) rr--;

    t[rr+1] = q[ll].crossPoint(q[rr]);

    ++rr, ++ll;

    if(rr - ll + 1 <= 2) return false;

    poly.n = rr - ll + 1;

    for(int i=ll;i<=rr;i++) poly.p[i-ll] = t[i];

    return true;

}

int main(){

#ifndef ONLINE_JUDGE

freopen("i.in","r",stdin);

//  freopen("o.out","w",stdout);

#endif

    scanf("%d", &T);

    while(T--){

        scanf("%d", &n);

        cin >> r >> A >> B;

        lawn.input(n);

        adjust();

        db total = lawn.getArea();

        db res = total * A;

        if(getHalfPlanes()) {

            db area = poly.getArea();

            db length = poly.getCircumference();

            area = area + length * r + pi * r * r;

            res = min(res, area * B + (total - area) * A);

        }

        cout << fixed << setprecision(20) << res << endl;

    }

    return 0;

}

巴特西

HDU 6762 Mow (2020 Multi-University Training Contest 1 1012）半平面交

Mow

分析

最新文章

热门文章

巴特西

HDU 6762 Mow (2020 Multi-University Training Contest 1 1012） 半平面交

Mow

分析

最新文章

热门文章

HDU 6762 Mow (2020 Multi-University Training Contest 1 1012）半平面交