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

Mow

题目链接

分析

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

需要用到的知识点：

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

另外需要注意的是该题目精度有些卡，需要用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;
}