程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 5091 給定矩形覆蓋盡量多點掃描線+線段樹

hdu 5091 給定矩形覆蓋盡量多點掃描線+線段樹

編輯：C++入門知識

hdu 5091 給定矩形覆蓋盡量多點掃描線+線段樹

給你10000以內的敵艦的坐標（即分別為x,y），要求用W*H的矩形去圍住一個區域，使得這個區域內的敵艦最多，矩形邊框上的敵艦也算在內。矩形可以平移，不能旋轉。

我們用矩形的中心點來描述這個矩形,然後對於每個敵艦,我們建立一個矩形中心的活動范圍,即矩形中心在該范圍內活動就可以覆蓋到該敵艦.那麼我們要求的問題就變成了:任意一個區域(肯定也是矩形的)最多能被矩形覆蓋的最大值.(即假如有價值為5和價值為3的矩形覆蓋了一個區域，那麼這片區域的價值為8).

在用線段樹離散化y軸坐標的時候發現線段樹上的每個葉節點表示的是一個半閉半開的區間[y1,y2),[y2,y3) 等.所以現在少了邊框上的敵艦的情況，這時只要把給定的w,h伸長0.5即可。

cnt:保存的是當前節點被覆蓋的值.
sum:表示該節點控制的區域內,被覆蓋的最大值.

所以向上更新方程為sum[i]=max(sum[i*2],sum[i*2+1]) + cnt[i];

#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
using namespace std;
#define RD(x) scanf(%d,&x)
#define RD2(x,y) scanf(%d%d,&x,&y)
#define RD3(x,y,z) scanf(%d%d%d,&x,&y,&z)
#define clr0(x) memset(x,0,sizeof(x))
#define clr1(x) memset(x,-1,sizeof(x))
#define eps 1e-9
const double pi = acos(-1.0);
typedef long long LL;
#define lson i*2,l,m
#define rson i*2+1,m+1,r
const int MAXN=20000+5;//因為點有1W個,所以掃描線2W個,不同的Y坐標最多有2W個
int cnt[MAXN*4],sum[MAXN*4];
double Y[MAXN];
struct seg
{
    double l,r,h;
    int d;
    seg(){}
    seg(double a,double b,double c,int d):l(a),r(b),h(c),d(d){}
    bool operator <(const seg&b)const
    {
        if(h == b.h) return d>b.d;
        return h>1;
    if(ql<=m) update(ql,qr,v,lson);
    if(m