70分求调
查看原帖
70分求调
422171
Gold_Dino楼主2023/11/29 21:01
#include<bits/stdc++.h>
using namespace std;
typedef complex<double> Complex;
Complex operator ~ (Complex z) {return conj(z);}
const double eps = 1e-6, Pi = 4 * atan(1);
bool ls(double a, double b) {return a - b < -eps;}
bool gr(double a, double b) {return a - b > eps;}
bool le(double a, double b) {return a - b < eps;}
bool ge(double a, double b) {return a - b > -eps;}
bool eq(double a, double b) {return abs(a - b) < eps;}
double dot(Complex a, Complex b) {return (~a * b).real();}
double cross(Complex a, Complex b) {return (~a * b).imag();}
const int N = 40011;
int n; double a, b, r;
struct Point {
    Complex z;
    double dis, the;
} p[N];
double ans;
bool comp1(Point a, Point b) {return ls(a.z.real(), b.z.real()) || (eq(a.z.real(), b.z.real()) && ls(a.z.imag(), b.z.imag()));}
bool comp2(Point a, Point b) {return ls(a.the, b.the) || (eq(a.the, b.the) && ls(a.dis, b.dis));}
double dis(Complex z) {return sqrt(z.real() * z.real() + z.imag() * z.imag());}
double dis(Complex a, Complex b) {return dis(a - b);}
Complex st[N]; int top;
int main() {
    int i;
    scanf("%d%lf%lf%lf", &n, &b, &a, &r);
    a = a / 2 - r;
    b = b / 2 - r;
    for(i = 1; i <= n; ++i) {
        double x, y, the;
        scanf("%lf%lf%lf", &x, &y, &the);
        Complex g = Complex(x, y), z = Complex(cos(the), sin(the));
        p[i].z = g + Complex(a, b) * z;
        p[i + n].z = g + Complex(a, -b) * z;
        p[i + n * 2].z = g + Complex(-a, b) * z;
        p[i + n * 3].z = g + Complex(-a, -b) * z;
    }
    n *= 4;
    sort(p + 1, p + n + 1, comp1);
    for(i = 2; i <= n; ++i) {
        Complex z = p[i].z - p[1].z;
        p[i].the = atan2(z.imag(), z.real());
        p[i].dis = dis(z);
    }
    sort(p + 2, p + n + 1, comp2);
    st[1] = p[1].z;
    st[2] = p[2].z;
    top = 2;
    for(i = 3; i <= n; ++i) {
        Complex now = p[i].z;
        while(top > 1) {
            Complex a = st[top - 1], b = st[top];
            if(le(cross(b - a, now - a), 0)) --top;
            else break;
        }
        ++top;
        st[top] = now;
    }
    n = top;
    st[0] = st[n];
    for(i = 1; i <= n; ++i) ans += dis(st[i - 1], st[i]);
    printf("%.2lf", ans + 2 * Pi * r);
    return 0;
}
2023/11/29 21:01
加载中...