程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 1828 &amp;&amp; POJ 1177 Picture(線段樹+掃描線+離散化）

HDU 1828 &amp;&amp; POJ 1177 Picture(線段樹+掃描線+離散化）

編輯：C++入門知識

HDU 1828 && POJ 1177 Picture(線段樹+掃描線+離散化）

HDU題目地址：HDU 1828 POJ題目地址：POJ 1177

這題是求周長並，我用的方法可能有點麻煩。。是先求橫著的線，再求豎著的線。每次只要求出每次的總區間覆蓋長度，然後每次累加這次的總區間覆蓋與上次的總區間覆蓋長度的差的絕對值。因為只有長度發生變化時，才會產生一段新的周長。

待會再試試只掃描一次的方法。此博客有待更新。

代碼如下：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1
int sum[50000], c[50000], cnt, a[6000], b[5000], d1[6000], d2[6000], lazy[50000];
struct node
{
    int l, r, h, f;
} edge[100000];
void add(int l, int r, int h, int f)
{
    edge[cnt].l=l;
    edge[cnt].r=r;
    edge[cnt].h=h;
    edge[cnt++].f=f;
}
int cmp(node x, node y)
{
    return x.h=r)
    {
        lazy[rt]+=x;
        PushUp(rt,l,r);
        return ;
    }
    int mid=l+r>>1;
    if(ll<=mid) update(ll,rr,x,lson);
    if(rr>mid) update(ll,rr,x,rson);
    PushUp(rt,l,r);
}
int erfen(int x, int high)
{
    int low=0, mid;
    while(low<=high)
    {
        mid=low+high>>1;
        if(c[mid]==x) return mid;
        else if(c[mid]>x) high=mid-1;
        else low=mid+1;
    }
}
int main()
{
    int n, i, j, last, ans, tmp, k;
    while(scanf("%d",&n)!=EOF)
    {
        cnt=0;
        k=0;
        memset(sum,0,sizeof(sum));
        memset(lazy,0,sizeof(lazy));
        for(i=0; i