首页 > 代码库 > poj1151Atlantis扫描线
poj1151Atlantis扫描线
第一道扫描线。
#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>using namespace std;const int maxn = 4004;double hash[maxn << 2];int color[maxn << 2];double sum[maxn << 2];#define lson l,mid,rt<<1#define rson mid+1,r,rt<<1|1struct Node{ int add; double l; double r; double h;}node[maxn << 2];int cmp(const Node&a, const Node &b){ return a.h<b.h;}void up(int l, int r, int rt){ if (color[rt]>0) sum[rt] = hash[r + 1] - hash[l]; //第 l个线段到 第r个线段的长度 = 第r+1个点与第l个点的距离 //else if (l == r) sum[rt] = 0; else sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];}void update(int L, int R, int add, int l, int r, int rt){ if (L <= l&&r <= R){ color[rt] += add; up(l, r, rt); return; } int mid = (l + r) >> 1; if (L <= mid) update(L, R, add, lson); if (R > mid) update(L, R, add, rson); up(l, r, rt);}int Bin(double key, double a[], int len)// 离散{ int l = 0; int r = len - 1; while (l <= r){ int mid = (l + r) >> 1; if (a[mid] == key) return mid; if (a[mid] < key) l = mid + 1; else r = mid - 1; } return -1;}int main(){ int n; double a, b, c, d; int gg = 0; while (cin >> n, n){ int m = 0; for (int i = 0; i < n; i++){ cin >> a >> b >> c >> d; hash[m] = a; node[m].l = a; node[m].r = c; node[m].h = b; node[m++].add = 1; hash[m] = c; node[m].l = a; node[m].r = c; node[m].h = d; node[m++].add = -1; } int k = 0; sort(hash, hash + m); sort(node, node + m, cmp); k++; for (int i = 1; i<m; i++) if (hash[i] != hash[i - 1]) hash[k++] = hash[i]; double ret = 0; for (int i = 0; i < m; i++){// 对最后一跟线扫完以后,sum与 color 都被清0了。 若是想手动初始化,就把 i<m 改为 i<m-1 int L = Bin(node[i].l, hash, k); int R = Bin(node[i].r, hash, k) - 1;//点变线段 比如 1(1) 2 (2) 3 (3) 4 update(L, R, node[i].add, 0, k - 1, 1); ret += sum[1] * (node[i + 1].h - node[i].h); } printf("Test case #%d\n", ++gg); printf("Total explored area: %.2f\n", ret); cout << endl; } return 0;}
poj1151Atlantis扫描线
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。