半平面交 模拟 双端队列
慢慢啃
人生第一次代码过两百行啊...加油加油
未来のために 頑張ってください
#include<iostream> #include<algorithm> #include<cmath> #include<cstring> #include<cstdio> #include<iomanip> #define ld long double using namespace std; const int maxn = 1e3; const ld pi = acosl(-1); const ld eps = 1e-10;//控制精度 int n; int head, tail; ld r, cost1, cost2; typedef struct Grid {//棋盘 ld x,y; Grid(double a = 0, double b = 0){x = a, y = b;}//构造函数,结构体对象创建时执行 } point , Vector ;//point:类型为Grid的数据类型;Vector与point结构相同,数据类型名称不同 typedef struct Net { point a,b; Net() {}//重载构造函数,目的是以形如line x;的方式定义直线,避免定义时确定参数的复杂性 Net(point i, point j){a = i, b = j;} } line ; point node[maxn], p[maxn]; line l[maxn], L[maxn], q[maxn]; Vector operator - (point a, point b) // V需大写,避免与vector混淆 { return Vector(b.x - a.x, b.y - a.y); }//矢量定义 double operator * (Vector a, Vector b) { return (a.x * b.y - a.y * b.x); }//叉乘 ld getangle(Vector t) { return atan2(t.y, t.x);//返回一个(-pi,pi]的角度 }//获得某个矢量的极角 ld getangle(line t) { return atan2(t.b.y - t.a.y, t.b.x - t.a.x); }//获得某条直线的极角 bool cmp(line a, line b) { Vector v1 = (a.b - a.a), v2 = (b.b - b.a); ld A = getangle(v1), B = getangle(v2); if(fabs(A - B) < eps){ return (v1 * (b.b - a.a) >= 0);//靠左边的丢在后面,方便双端队列去重 } return A < B; }//决定根据极角排序的直线的优先级 bool check() { ld ans = 0; for(int i = 1 ; i < n-1 ; i++){ ans += (node[i] - node[0]) * (node[i+1] - node[0]); } if(ans < 0) return false; return true; }//检查point输入顺序进行调整 true为逆时针 point getnode(line a, line b)//求两直线(线段)交点,一般式三参数暴力求解 { ld a1 = a.b.y - a.a.y, b1 = a.a.x - a.b.x, c1 = a.b.x * a.a.y - a.a.x * a.b.y; ld a2 = b.b.y - b.a.y, b2 = b.a.x - b.b.x, c2 = b.b.x * b.a.y - b.a.x * b.b.y; ld D = a1 * b2 - a2 * b1; //Dx/D,Dy/D,注意c1、c2移至右侧变号 return point((c2 * b1 - b2 * c1) / D, (c1 * a2 - a1 * c2) / D); } bool on_right(line a, line b, line c)//观察a、b交点与c的关系 { point n = getnode(a, b); if((c.b - c.a) * (n - c.a) < 0){//交点在右侧/下方 return true; } return false; } line narrow_line(line x)//实现直线平移,勾画出圆心轨迹 { ld dx = x.b.x - x.a.x, dy = x.b.y - x.a.y; Vector turnv;//旋转矢量 turnv.x = -dy, turnv.y = dx; ld m = sqrtl(dx * dx + dy * dy); turnv.x = turnv.x / m * r; turnv.y = turnv.y / m * r; //求对应坐标 x.b.x += turnv.x; x.b.y += turnv.y; x.a.x += turnv.x; x.a.y += turnv.y; return x; } void narrow_polygon()//模拟圆心轨迹 { for(int i = 0 ; i <= n-1 ; i++){ L[i] = narrow_line(l[i]); } } bool HPI() { sort(L,L+n,cmp);//按极角排序 head = 0, tail = 0; int cnt = 0; for(int i = 0 ; i < n-1 ; i++){ Vector v1 = L[i].b - L[i].a, v2 = L[i+1].b - L[i+1].a;//? if(fabs(getangle(v1) - getangle(v2)) < eps){ continue; } L[cnt++] = L[i]; } L[cnt++] = L[n-1]; /////正片开始 for(int i = 0 ; i < cnt ; i++){//注意下标 while(tail - head > 1 && on_right(q[tail-1], q[tail-2], L[i])) tail--;//符合onright规则,删去上一条直线 while(tail - head > 1 && on_right(q[head], q[head+1], L[i])) head++;//头部同理 q[tail++] = L[i]; } //换个角度看世界,最后检验q[head]以及q[tail-1],q[tail]实际为空 while(tail - head > 1 && on_right(q[tail-1], q[tail-2], q[head])) tail--; while(tail - head > 1 && on_right(q[head], q[head+1], q[tail-1])) head++; if((tail - head) >= 3) return true; return false; } ld get_S()//求初始面积 { ld ans = 0; for(int i = 1 ; i < n ; i++){ ans += fabs((node[i] - node[0]) * (node[(i+1)%n] - node[0])); } return ans / 2; } ld dis(point a, point b) { ld dx = b.x - a.x, dy = b.y - a.y; return sqrtl(dx * dx + dy * dy); }//两点间距离 ld get_inS()//内部半平面交 面积 { ld res = 0; int tot = 0; for(int i = head ; i < tail-1 ; i++){ p[tot++] = getnode(q[i], q[i+1]); } p[tot++] = getnode(q[tail-1], q[head]); for(int i = 1 ; i < tot-1 ; i++){ res += fabs((p[i] - p[0]) * (p[i+1] - p[0])); } res /= 2; for(int i = 0 ; i < tot-1 ; i++){ res += dis(p[i], p[i+1]) * r; }// c * r res += dis(p[0], p[tot - 1]) * r; return res + r * r * pi; } int main(){ //freopen("mow.in","r",stdin); int T;cin >> T; while( T-- ) { cin >> n >> r >> cost1 >> cost2; for(int i = n-1 ; i >= 0 ; i--){ cin >> node[i].x >> node[i].y; }//本题中为顺时针方向,因而逆序存点,以确保直线左侧为内侧 if(check()){//逆 for(int i = 0 ; i < n-1 ; i++){// l[i] = line(node[i], node[i+1]); } l[n-1] = line(node[n-1], node[0]); }else{//顺 for(int i = 0 ; i < n-1 ; i++){ l[i] = line(node[i+1],node[i]); } l[n-1] = line(node[0], node[n-1]); }//0 ~ n-1 narrow_polygon(); ld s = get_S();//草坪面积 ld ans = s * cost1;//手动割草费用 if(HPI()){ ld mowable = get_inS();//机器割草面积 ans = min(ans, mowable * cost2 + (s - mowable) * cost1); } cout << fixed << setprecision(25) << ans << "\n"; } return 0; }
//实现直线平移,勾画出圆心轨迹