POJ 2482

題意：二維平面很多星星，每個星星有亮度，給個矩形框，要求裝進去的最大亮度之和（題目圖檔上面n長的英語表白模闆是亮點）

題解：掃描線+區間最大值，不過應該還有更快的方法吧，或者就是寫慫了..注意雖然題目給的資料是在int範圍内的，但是加上h後可能會超，是以嫌麻煩就全用long long好了。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct point
{
    long long x,y,val;
};
inline bool compx(const point &a,const point &b)
{
    return (a.x==b.x)?(a.y<b.y):(a.x<b.x);
}
inline bool compy(const point &a,const point &b)
{
    return (a.y==b.y)?(a.val<b.val):(a.y<b.y);
}
const long long N=10005;
point po[N],temp[2*N];
long long getmax(int n)
{
    long long ans=0,d=0;
    for(int i=0;i<n;i++)
    {
        if(d<=0)
            d=temp[i].val;
        else
            d+=temp[i].val;
        ans=max(d,ans);
    }
    return ans;
}
long long solve(int i,int j,long long h)
{
    int n=j-i;
    memcpy(temp,po+i,n*sizeof(point));
    i=0;j=n;
    n*=2;
    while(j<n)
    {
        temp[j].y=temp[i].y+h;
        temp[j].x=temp[i].x;
        temp[j].val=-temp[i].val;
        i++,j++;
    }
    sort(temp,temp+n,compy);
    return getmax(n);
}
int main()
{
    long long n,w,h;
    while(scanf("%lld%lld%lld",&n,&w,&h)!=EOF)
    {
        for(int i=0;i<n;i++)
            scanf("%lld%lld%lld",&po[i].x,&po[i].y,&po[i].val);
        sort(po,po+n,compx);
        long long ans=0;
        for(int i=0,j=0;j<n&&i<n;i++)
        {
            while(i>0&&i<n&&po[i].x==po[i-1].x)
                i++;
            while(j<n&&po[j].x-po[i].x<w)
                j++;
            ans=max(ans,solve(i,j,h));
        }
        printf("%lld\n",ans);
    }
    return 0;
}