这个题是拉格朗日数乘法的裸题。

我做PE的时候了解到的这种方法, 据说是高考几大艹标算大法之一?

看来我这个高考狗就是和这种奇技淫巧有缘分啊。

传送门

题目大意

实现以下3种操作:

  1. 平面上加入一条直线;

  2. 删除一条已加入的直线;

  3.  求一个点到平面上所有直线距离平方和最小,你需要输出这个最小值。

解题报告

一个点\((x_0, y_0)\)到直线\(Ax+By+C = 0\)的距离平方公式是 \[ \frac{(Ax_0+By_0+C)^2}{A^2+B^2} \] 然后就可以把距离平方和表示成\(ax^2+by^2+cxy+dx+ey+f\)的鬼畜样子。

然后对\(x, y\)分别求一发偏导, 令两个式子都等于零。

就把\(x, y\)算出来了。

各种操作复杂度都是\(O(1)\)的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
#define rep(i,a,b) for(int i=int(a),nn=int(b);i<=nn;++i)
#define vep(i,a,b) for(int i=int(a),nn=int(b);i>=nn;--i)
#define xep(i,b) for(int i=0,nn=int(b);i<nn;++i)
typedef double ff;
const int N=120010;
ff a[N],b[N],c[N],A,B,C,D,E,F;
void print(ff x) {
if(fabs(x)<1e-6)puts("0.00");else printf("%.2lf\n",fabs(x));
}
ff f[3][4],ansx,ansy;
inline void solve() {
int i,j,k;ff t;int n=2;
if(fabs(f[1][1])<1e-6) {
if(fabs(f[1][2])<1e-6)ansx=0,ansy=f[2][3]/f[2][2];
else ansy=f[1][3]/f[1][2],ansx=(f[2][3]-f[2][2]*ansy)/f[2][1];
return;
}
if(fabs(f[2][2])<1e-6) {
if(fabs(f[2][1])<1e-6)ansx=f[1][3]/f[1][1],ansy=0;
else ansx=f[2][3]/f[2][1],ansy=(f[1][3]-f[1][1]*ansx)/f[1][2];
return;
}
t=-f[2][1]/f[1][1];f[2][1]=0,f[2][2]+=t*f[1][2],f[2][3]+=t*f[1][3];
f[2][3]=(fabs(f[2][2])<1e-6)?0:f[2][3]/f[2][2],f[1][3]-=f[1][2]*f[2][3],f[1][3]/=f[1][1];
ansx=f[1][3],ansy=f[2][3];
}
int main() {
ff x0,y0,x1,y1,t; int num=0,cnt,now=0;
int q,tp,del; scanf("%d",&q);
while(q--) {
scanf("%d",&tp);
if(tp==0) {
scanf("%lf%lf%lf%lf",&x0,&y0,&x1,&y1);
cnt=++num; ++now;
a[cnt]=y0-y1,b[cnt]=x1-x0,c[cnt]=y0*(x0-x1)-x0*(y0-y1);
t=a[cnt]*a[cnt]+b[cnt]*b[cnt];
A+=a[cnt]*a[cnt]/t,B+=b[cnt]*b[cnt]/t;C+=2*a[cnt]*b[cnt]/t;
D+=2*a[cnt]*c[cnt]/t,E+=2*b[cnt]*c[cnt]/t,F+=c[cnt]*c[cnt]/t;
}
else if(tp==1) {
scanf("%d",&del);
cnt=del,t=a[cnt]*a[cnt]+b[cnt]*b[cnt],--now;
A-=a[cnt]*a[cnt]/t,B-=b[cnt]*b[cnt]/t,C-=2*a[cnt]*b[cnt]/t;
D-=2*a[cnt]*c[cnt]/t,E-=2*b[cnt]*c[cnt]/t,F-=c[cnt]*c[cnt]/t;
}
else{
if(now==0) {puts("0.00");continue;}
f[1][1]=2*A,f[1][2]=C,f[1][3]=-D,f[2][1]=C,f[2][2]=2*B,f[2][3]=-E;
solve();
print(A*ansx*ansx+B*ansy*ansy+C*ansx*ansy+D*ansx+E*ansy+F);
}
}
return 0;
}

留言