程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU-1542-Atlantis-線段樹+面積並（模板）

HDU-1542-Atlantis-線段樹+面積並（模板）

編輯：C++入門知識

HDU-1542-Atlantis-線段樹+面積並（模板）

但是我覺得他們寫的都不太詳細，缺少步驟，像我這種菜鳥，就花了一上午，才搞定這一題；

對於新學，我覺得還是有詳細的步驟會更好的幫助理解；所以我就手畫了一張步驟圖，以及線段數怎麼建的（orz,不會用那些高級的制圖工具，so...）

首先建樹，每個節點維護一個連續的區間；

總共4條豎向線段，所以共有4步插入查詢，每次cover>0 說明有交面積，分步求；詳細的請看圖。。。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long
#define inf 1<<30
using namespace std;
const int N=205;
int n;
double y[N];
struct LINE     //  存儲線段信息；
{
    double x;   //  該線段所在的位置；
    double y_up,y_down;     //  豎向線段的上下端點；
    int flag;
}line[N];
struct node
{
    double l,r;
    double x;       //  記錄上一個橫坐標位置，用於求面積；
    int cover;      //  記錄覆蓋的線段數；即同一方向的線段數；
    bool flag;      //  標記只有一個區間的節點，即10-15，15-20這是一個區間，我們將一個一個連續的區間離散化成一個節點；
}node[N<<2];
bool cmp(LINE a,LINE b)
{
    return a.x>1;
    build(rt<<1,l,mid);
    build(rt<<1|1,mid,r);   //  同42行，所以此處mid不需要+1；
}
double Insert_query(int rt,double x,double l,double r,int flag) //  查詢+更新x處（l,r）區間面積；
{
    if(l>=node[rt].r||r<=node[rt].l) return 0;  //  該方向節點不包含所要查詢的區間；
    if(node[rt].flag){  //  找到只有一個區間的葉子節點；
        if(node[rt].cover>0){
            double pre=node[rt].x;
            double ans=(x-pre)*(node[rt].r-node[rt].l); //  計算面積；
            node[rt].x=x;       //  更新定位上一下x位置，便於下次計算面積；
            node[rt].cover+=flag;   //  更新覆蓋的線段數；
            return ans;
        }else{
            node[rt].x=x;
            node[rt].cover+=flag;
            return 0;
        }
    }
    double ans1,ans2;
    ans1=Insert_query(rt<<1,x,l,r,flag);    //  直接往兩個方向查，算有符合區間的面積；
    ans2=Insert_query(rt<<1|1,x,l,r,flag);  //  52行保證查詢的可行性；
    return ans1+ans2;
}
int main()
{
    int Case=0;
    double x1,x2,y1,y2;
    while(~scanf(%d,&n)&&n){
        int cnt=-1;
        for(int i=0;i