求助 POJ 1151
  • 板块学术版
  • 楼主Register_int-std=c++14
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/10/2 08:46
  • 上次更新2023/10/27 09:16:30
查看原帖
求助 POJ 1151
406941
Register_int-std=c++14楼主2022/10/2 08:46

rt,目前已确认不是精度问题,不是输出格式问题,不是精度问题,可他还是WA啊啊啊啊啊啊啊啊啊求大佬帮忙

#include <iostream>
#include <algorithm>
#include <map>
#include <cstring>

using namespace std;

typedef long double db;

const int MAXN = 2e2 + 10;

struct Line {
    db l, r, h;
    int mark;
    Line() {}
    Line(db l, db r, db h, int mark) : l(l), r(r), h(h), mark(mark) {}
    bool operator < (const Line &p) const { return h < p.h; }
} line[MAXN << 1]; 

int tot;

db num[MAXN << 1];

struct segtree {
    int l, r, cnt;
    db len;
} t[MAXN << 2];

inline 
void pushup(int p) {
    if (t[p].cnt) t[p].len = num[t[p].r + 1] - num[t[p].l];
    else t[p].len = t[p << 1].len + t[p << 1 | 1].len;
}

void build(int l, int r, int p) {
    t[p].l = l, t[p].r = r;
    if (l == r) return ;
    int mid = l + r >> 1;
    build(l, mid, p << 1), build(mid + 1, r, p << 1 | 1);
}

void add(db l, db r, int k, int p) {
    if (num[t[p].r + 1] <= l || r <= num[t[p].l]) return ;
    if (l <= num[t[p].l] && num[t[p].r + 1] <= r) return t[p].cnt += k, pushup(p);
    add(l, r, k, p << 1), add(l, r, k, p << 1 | 1);
    pushup(p);
}

int n, c;

db ax, ay, bx, by, ans;

int main() {
    while (~scanf("%d", &n) && n) {
    	for (int i = 1; i <= n; i++) {
	        scanf("%Lf%Lf%Lf%Lf", &ax, &ay, &bx, &by);
	        num[++tot] = ax, line[tot] = Line(ax, bx, ay, 1);
	        num[++tot] = bx, line[tot] = Line(ax, bx, by, -1);
	    }
	    sort(line + 1, line + tot + 1);
	    sort(num + 1, num + tot + 1);
	    n = tot, tot = unique(num + 1, num + tot + 1) - num - 1;
	    build(1, tot - 1, 1);
	    for (int i = 1; i < n; i++) {
	        add(line[i].l, line[i].r, line[i].mark, 1);
	        ans += t[1].len * (line[i + 1].h - line[i].h);
	    }
	    printf("Test case #%d\nTotal explored area: %.2Lf\n\n", ++c, ans);
	    tot = ans = 0;
	    memset(t, 0, sizeof t);
	    memset(num, 0, sizeof num);
	    memset(line, 0, sizeof line);
	}
}
2022/10/2 08:46
加载中...