70pts求调
  • 板块P1222 三角形
  • 楼主Kendieer
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/11/29 13:20
  • 上次更新2024/11/29 16:53:07
查看原帖
70pts求调
448268
Kendieer楼主2024/11/29 13:20

WA 3,4,6,求调。

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define rep(i,a,b) for(ll i = (a);i < (b);i++)
#define repr(i,a,b) for(ll i = (b) - 1;i>= (a);i--)
#define elif else if
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
const ll inf = 0x3f7f7f7f7f7f7f7f;

ll qread(){
    ll r = 0,s = 1,ch = getchar();
    while (ch == ' ' || ch == '\r' || ch == '\n') ch = getchar();
    if (ch == '-') ch = getchar(),s = -1;
    while (ch >= '0' && ch <= '9') r = r * 10 + ch - '0',ch = getchar();
    return r * s;
}
template <typename ... Args>
void qread(Args&&... e){
    ((e = qread()), ...);
}

char readChar(){
    int ch = getchar();
    while (ch == ' ' || ch == '\r' || ch == '\n') ch = getchar();
    return ch;
}

const string QWrite = "0123456789ABCDEF";
void qwrite(ll x,int t = 10){
    if (x>=t) qwrite(x/t,t);
    putchar(QWrite[x%t]);
}

const int maxn = 2e3 + 7;
const int mod = 998244353;
struct Node {
    ll x,y,wid;
} nodes[maxn];

struct Edge{
    ll pos,add,id;
    Edge(ll pos = -inf,ll add = 0,ll id = -1):pos(pos),add(add),id(id){}
};
vector<Edge> x,y;
set<ll> xpos;

bool cmp(Node a,Node b){
    if (a.x == b.x) return a.y>b.y; 
    return a.x < b.x;
}

bool cmp_pnt(Edge a,Edge b){
    if (a.pos == b.pos ) return a.add < b.add;
    return a.pos < b.pos;
}

bool isIn(ll x1,ll x2,int id){
    return (x1 >= nodes[id].x && x1 <= nodes[id].x+nodes[id].wid && x2 >= nodes[id].x && x2 <= nodes[id].x + nodes[id].wid);
}

void solve(){
    int n = qread();
    rep(i,0,n){
        nodes[i].x = qread();
        nodes[i].y = qread();
        nodes[i].wid = qread();
        // x.push_back(Edge(nodes[i].x,1,i));
        // x.push_back(Edge(nodes[i].x+nodes[i].wid,-1,i));
        xpos.insert(nodes[i].x);
        xpos.insert(nodes[i].x+nodes[i].wid);
        y.push_back(Edge(nodes[i].y,1,i));
        y.push_back(Edge(nodes[i].y+nodes[i].wid,-1,i));
    }
    // sort(nodes,nodes+n,cmp);
    // sort(x.begin(),x.end(),cmp_pnt);
    double ans = 0;
    // ll dx = 0;
    ll last = -inf;
    for(auto &xp:xpos){
        // cout << xp << ":" << endl;
        if (last == -inf) {
            last = xp;
            continue;
        }
        sort(y.begin(),y.end(),cmp_pnt);
        ll dep =0,lst = -inf,h = xp-last;
        rep(j,0,y.size()){
            if (isIn(last,xp,y[j].id)){
                dep += y[j].add;
                if (y[j].add == 1){
                    if (dep == 1){
                        lst = y[j].pos;
                        // cout << y[j].pos << " ";
                    }
                } else {
                    if (dep == 0){
                        ll w = y[j].pos - lst;
                        ans += (w*2-h)*h/2.0;
                    }
                    y[j].pos -= h;
                }
            }
        }
        // cout << endl;
        last = xp;
    }
    printf("%.1f",ans);
}

int main(){
//     int n = qread();
//     while(n--)
    solve();
    return 0;
}
2024/11/29 13:20
加载中...