萌新初学寄蒜积和,简单凸包板子题 WA+TLE 0 分 求调
查看原帖
萌新初学寄蒜积和,简单凸包板子题 WA+TLE 0 分 求调
378467
Windy_YY楼主2024/7/19 11:30

rt,自己造的数据和样例都可以通过了。

bool begmem;
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 300010;
using POD = pair<double, double>;
#define x first
#define y second
double cross(POD q, POD b) {
    return q.x * b.y - q.y * b.x;
}
POD operator-(const POD &l, const POD &r) {
    return {l.x - r.x, l.y - r.y};
}
double dist(POD q, POD b) {
    return sqrt((q.x - b.x) * (q.x - b.x) + (q.y - b.y) * (q.y - b.y));
}
double area(POD q, POD b, POD c) {
    return abs(cross(b - q, c - q));
}
POD q[N];
int n, top, stk[N], used[N];
// vector<POD> andrew() {
//     sort(q, q + n);
//     int top = 0;
//     for (int i = 0; i < n; ++i) {
//         while (top >= 2 && area(q[stk[top - 1]], q[stk[top]], q[i]) <= 0) used[stk[top--]] = 0;
//         stk[++top] = i, used[i] = 1;
//     }
//     used[0] = 0;
//     for (int i = n - 1; ~i; --i)
//         if (!used[i]) {
//             while (top >= 2 && area(q[stk[top - 1]], q[stk[top]], q[i]) <= 0) --top;
//             stk[++top] = i;
//         }
//     vector<POD> res;
//     for (int i = 1; i <= top; ++i) res.emplace_back(q[stk[i]]);
//     return res;
// }
vector<POD> andrew() {
    int top=0;
    stk[0]=1;
	stk[1]=2;
	for(int i=3;i<=n;++i){
		while(top&&area(q[stk[top-1]],q[stk[top]],q[i])<=0)--top;
		stk[++top]=i;
	}
	stk[++top]=n-1;
	for(int i=n-2;i>0;--i){
		while(top>1&&area(q[stk[top-1]],q[stk[top]],q[i])<=0)--top;
		stk[++top]=i;
	}
    vector<POD> res;
    for(int i=1;i<=top;++i)res.emplace_back(q[stk[i]]);
    return res;
}
struct Lin {
    POD x, y;
} ;
int len(POD x) {
    return x.first * x.first + x.second * x.second;
}
double tolin(POD p, Lin x) {
    POD p1 = x.y, p2 = p - x.x;
    return abs(cross(p1, p2));
}
double roating(vector<POD> tubao) {
    if (tubao.size() == 3)
        return len(tubao[1] - tubao[0]);
    int p = 0, mx = 0;
    for (int i = 0; i < (int)tubao.size() - 1; ++i) {
        POD l1 = tubao[i + 1] - tubao[i];
        while (abs(cross(l1, tubao[p] - tubao[i])) <= abs(cross(tubao[p + 1] - tubao[i], l1)))
            p = (p + 1) % ((int)tubao.size() - 1);
        mx = max({mx, len(tubao[i] - tubao[p]), len(tubao[i + 1] - tubao[p])});
    }
    return mx;
}
double area(vector<POD> tubao) {
    tubao.pop_back();
    if (tubao.size() >= 3) {
        double mx = 0;
        for (int i = 0; i < tubao.size(); ++i) {
            int p1 = (i + 1) % tubao.size(), p2 = (i + 3) % tubao.size();
            for (int j = (i + 2) % tubao.size(); j != i; j = (j + 1) % tubao.size()) {
                while (p1 != j && area(tubao[i], tubao[j], tubao[p1]) < area(tubao[i], tubao[j], tubao[p1 + 1])) p1 = (p1 + 1) % tubao.size();
                while (p2 != i && area(tubao[i], tubao[j], tubao[p2]) < area(tubao[i], tubao[j], tubao[p2 + 1])) p2 = (p2 + 1) % tubao.size();
                mx = max(mx, area(tubao[i], tubao[j], tubao[p1]) + area(tubao[i], tubao[j], tubao[p2]));
                // printf("%lf %lf %lf %lf %lf %lf %lf %lf: ", tubao[i].first, tubao[i].second, tubao[j].first, tubao[j].second, tubao[p1].first, tubao[p1].second, tubao[p2].first, tubao[p2].second);
                // printf("%lld %lld %lld %lld %lf %lf\n", i, j, p1, p2, area(tubao[i], tubao[j], tubao[p1]), area(tubao[i], tubao[j], tubao[p2]));
            }
        }
        return mx;
    } else {
        return 0;
    }
}
void solveqwq() {
    scanf("%lld", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%lf%lf", &q[i].x, &q[i].y);
    printf("%.3lf\n", area(andrew()) / 2);
}
void calcqwq();
signed main() {
    atexit(calcqwq);
    int T = 1;
    clock_t stk = clock();
    while (T--) solveqwq();
    clock_t ed = clock();
    fprintf(stderr, "Time Used %.5lf second(s).\n", 1. * (ed - stk) / CLOCKS_PER_SEC);
}
bool endmem;
void calcqwq() {
    fprintf(stderr, "Memory = %.5lf\n", (&begmem - &endmem) / 1048576.);
}

/*

5
0 0
1 0
2 1
2 2
1 2

*/
2024/7/19 11:30
加载中...