首页 > 代码库 > 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扫描线