BZOJ1896 Equations 线性规划+半平面交+三分

题意简述

给你\(3\)个数组\(a_i\)，\(b_i\)和\(c_i\)，让你维护一个数组\(x_i\)，共\(m\)组询问，每次给定两个数\(s\)，\(t\)，使得

\[\sum_i a_i x_i = s \qquad \sum_i b_i x_i = t
\]

让你求出\(\mathrm{Maximize} \sum_i c_i x_i\)。

做法

显然题目是一个线性规划的模型，用\(x\)，\(y\)表示两个新变量，使用对偶转化可得

\[\begin{split}
&\mathrm{Minimize} \qquad &sx+ty \\
&\mathrm{Satisfy} \qquad &\forall i , a_ix+b_iy \geq c_i \\
& &x,y \in R
\end{split}
\]

发现可以用半平面交维护，所以预处理半平面交，对于\(sx+ty\)将其转成一条直线，二分/三分找极值即可，复杂度\(O((n+m) \log n)\)。

Code

#include<bits/stdc++.h>

using namespace std;

#define re register int

#define db double

#define ll long long

#define in inline

#define ak *

in char getch()

{

    static char buf[10000],*p1=buf,*p2=buf;

    return p1==p2&&(p2=(p1=buf)+fread(buf,1,10000,stdin),p1==p2)?EOF:*p1++;

}

#define gc() getch()

char qwq;

in int read()

{

    re cz=0,ioi=1;qwq=gc();

    while(qwq<'0'||qwq>'9') ioi=qwq=='-'?~ioi+1:1,qwq=gc();

    while(qwq>='0'&&qwq<='9') cz=(cz<<3)+(cz<<1)+(qwq^48),qwq=gc();

    return cz ak ioi;

}

const db inf=1e18,eps=1e-11;

const int N=1e5+5;

int n,m,k,top,tot;

db s,t;

struct poi{

	db x,y;

	poi(db _x=0,db _y=0) {x=_x,y=_y;}

}p[N];

struct line{

	db k,b;

	line(db _k=0,db _b=0) {k=_k,b=_b;}

	in bool operator <(line x) const {return k==x.k?b>x.b:k<x.k;}

	in poi operator &(line x) {return poi((x.b-b)/(k-x.k),(k*x.b-x.k*b)/(k-x.k));}

}e[N],q[N];

in db calc(re x) {return p[x].x*s+p[x].y*t;}

int main()

{

	n=read();k=read();

	for(re i=1;i<=n;i++)

	{

		db a=read(),b=read(),c=read();

		e[++m]=line(-a/b,c/b);

	}

	sort(e+1,e+m+1);

	for(re i=1;i<=m;i++)

	{

		if(top&&q[top].k==e[i].k) continue;

		while(top>1&&(q[top]&q[top-1]).y<=(q[top]&q[top-1]).x*e[i].k+e[i].b) top--;

		q[++top]=e[i];

	}

	for(re i=1;i<top;i++) p[++tot]=q[i]&q[i+1];

	for(re i=1;i<=k;i++)

	{

		s=read(),t=read();

		if(-s/t>q[top].k||-s/t<q[1].k) puts("IMPOSSIBLE");

		else

		{

			db res=inf;re l=1,r=tot;

			while(l<=r)

			{

				re ml=l+(r-l)/3,mr=r-(r-l)/3;

				db cl=calc(ml),cr=calc(mr);

				if(cl<cr) r=mr-1,res=cr;

				else l=ml+1,res=cl;

			}

			printf("%.5lf\n",res);

		}

	}

}