BZOJ 4614[Wf2016]Oil

时间:2023-03-08 16:27:12

权限题鸭qwq

首先可以知道最优答案选出来的直线一定可以经过某条线段左端点,如果这条直线没有过左端点,可以通过平移和旋转等操作达到.所以可以枚举这条直线过了哪条线段的左端点,那么对于其他线段,能对答案产生贡献当且仅当该直线的斜率 在 选出的左端点分别和线段两端点连线 构成的斜率区间内.所以将斜率离散后每条线段会对某段区间加上该线段长度,那么只要求单点最大值就行了,可以差分处理

然而一直lower_bound,慢的飞起,吸氧卡过去的qwq

//大力爆搜------走错片场了???
#include<bits/stdc++.h>
#define LL long long
#define il inline
#define re register
#define db double
#define eps (1e-5) using namespace std;
const int N=2000+10;
il LL rd()
{
LL x=0,w=1;char ch=0;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
struct node
{
int x,y;
node(){}
node(int nwx,int nwy){x=nwx,y=nwy;if(y<0) x=-x,y=-y;}
bool operator < (const node &bb) const {return 1ll*x*bb.y<1ll*y*bb.x;}
bool operator == (const node &bb) const {return 1ll*x*bb.y==1ll*y*bb.x;}
}b[N<<1];
int n,m,a[N][3],s[N<<1],an,ans; int main()
{
n=rd();
for(int i=1;i<=n;i++)
{
a[i][0]=rd(),a[i][1]=rd(),a[i][2]=rd();
if(a[i][0]>a[i][1]) swap(a[i][0],a[i][1]);
}
for(int i=1;i<=n;i++)
{
m=0;
for(int j=1;j<=n;j++)
{
if(i==j||a[i][2]==a[j][2]) continue;
b[++m]=node((a[j][0]-a[i][0]),(a[j][2]-a[i][2])),b[++m]=node((a[j][1]-a[i][0]),(a[j][2]-a[i][2]));
}
sort(b+1,b+m+1);
m=unique(b+1,b+m+1)-b-1;
memset(s,0,sizeof(s));
for(int j=1;j<=n;j++)
{
if(i==j||a[i][2]==a[j][2]) continue;
int ll=lower_bound(b+1,b+m+1,node((a[j][0]-a[i][0]),(a[j][2]-a[i][2])))-b,rr=lower_bound(b+1,b+m+1,node((a[j][1]-a[i][0]),(a[j][2]-a[i][2])))-b;
if(ll>rr) swap(ll,rr);
s[ll]+=a[j][1]-a[j][0],s[rr+1]-=a[j][1]-a[j][0];
}
an=0;
for(int j=1;j<=m;j++)
{
s[j]+=s[j-1];
an=max(an,s[j]);
}
ans=max(ans,an+a[i][1]-a[i][0]);
}
printf("%d\n",ans);
return 0;
}