2019牛客暑期多校训练（第九场）J-Symmetrical Painting

---

日常膜拜：
膜拜鑫爹昊妈还有博文大佬

---

---

题意

给定n个宽为1的矩形，将某些区域删去，使得剩下的图形有一条平行于x轴的对称轴，问怎样使得面积最大，输出最大的面积

思路

易知，对称轴只可能出现在矩形的两端或者中点处。（如果不在这三个点则面积不会发生突变，即不是极值点）
用扫描线去挨个扫过这些可能的点，计算面积，求最大值即可。

坑点

想不到

---

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=3e5+5;

double top[N],down[N];
double mid[N];
double all[3*N];

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%lf%lf",&down[i],&top[i]);
        mid[i]=(down[i]+top[i])/2;
        all[3*i]=down[i];
        all[3*i+1]=top[i];
        all[3*i+2]=mid[i];
    }
    sort(down,down+n);
    sort(mid,mid+n);
    sort(top,top+n);
    sort(all,all+3*n);
//    for(int i=0;i<n;i++)
//    {
//        cout<<down[i]<<' ';
//    }
//    cout<<endl;
//    for(int i=0;i<n;i++)
//    {
//        cout<<mid[i]<<' ';
//    }
//    cout<<endl;
//    for(int i=0;i<n;i++)
//    {
//        cout<<top[i]<<' ';
//    }
//    cout<<endl;
//    for(int i=0;i<3*n;i++)
//    {
//        cout<<all[i]<<' ';
//    }
//    cout<<endl;
    int cntdown=0,cntmid=0,cnttop=0;
    int num1=0,num2=0;
    double maxn=0;
    double sum=0;
    for(int lin=1;lin<3*n;lin++)
    {
        while(cntdown<n&&down[cntdown]<all[lin])
        {
            cntdown++;
            num1++;
        }
        while(cntmid<n&&mid[cntmid]<all[lin])
        {
            cntmid++;
            num1--;
            num2++;
        }
        while(cnttop<n&&top[cnttop]<all[lin])
        {
            cnttop++;
            num2--;
        }
        sum=sum+num1*(all[lin]-all[lin-1])-num2*(all[lin]-all[lin-1]);
        maxn=max(maxn,sum);
    }
    printf("%lld\n",(ll)(2*maxn));
    return 0;
}