bzoj 2508: 简单题 — 数学

 

2508: 简单题

Time Limit: 10 Sec  Memory Limit: 512 MB Sec  Special Judge

Description

求一个点使得它到平面上所有直线距离平方和最小。
你需要实现以下3种操作:
1.       平面上加入一条直线;
2.       删除一条已加入的直线;
3.       求一个点到平面上所有直线距离平方和最小,你需要输出这个最小值。

Input

第1行包含一个整数N,表示了操作数目。接下来N行操作属于下列3种格式之一:

Output

输出行数等于查询操作的次数,每行输出每次查询操作所要求的最小值,保留两位小数。

Sample Input

10
0 0.0 0.0 1.0 0.0
2
0 0 1 1 1
2
0 0 2 1 2
2
1 2
2
1 3
2
 

Sample Output

0.00
0.50
2.00
2.00
0.00
【数据规模与约定】
对于10%的数据,N ≤ 25;
对于50%的数据,N ≤ 1000;
对于50%的数据,查询操作不超过10次;
对于70%的数据,N ≤ 20000;
对于100%的数据,N ≤ 120000。

HINT

一个点到直线Ax+By+C=0 的距离的平方公式是

所以我们就可以展开化简成

那么,怎么求他的最值

对于一个正常函数,求最值可求导,导数为0 时就是最值

那么对于一个多变量的函数,我们可以分别对于每一个变量求 (偏)导,得到的解就是最值所在的位置

关于偏导具体可以看一下维基或者百度百科

然后就求一下偏导算一下就好了,剩下就是细节问题了

#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define inf 1000000007
#define ll long long
#define N 120010
#define db double
struct qaz{db a,b,c;}a[N];
int n,tot,ji;
db x,y,xx,yy;
db A,B,C,D,E,F;
void ins()
{
	int p=++tot;ji++;
	a[p].a=y-yy;a[p].b=xx-x;a[p].c=y*(x-xx)-x*(y-yy);
	db tp=(a[p].a*a[p].a+a[p].b*a[p].b);
	A+=a[p].a*a[p].a/tp;B+=a[p].b*a[p].b/tp;
	C+=2*a[p].a*a[p].b/tp;D+=2*a[p].a*a[p].c/tp;
	E+=2*a[p].b*a[p].c/tp;F+=a[p].c*a[p].c/tp;
}
void del(int p)
{
	ji--;db tp=(a[p].a*a[p].a+a[p].b*a[p].b);
	A-=a[p].a*a[p].a/tp;B-=a[p].b*a[p].b/tp;
	C-=2*a[p].a*a[p].b/tp;D-=2*a[p].a*a[p].c/tp;
	E-=2*a[p].b*a[p].c/tp;F-=a[p].c*a[p].c/tp;
}
db ans,f[3][4];
#define eps 1e-5
void sol()
{
	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;
	db tx,ty,tt;
	if(abs(f[1][1])<eps)
	{
		if(abs(f[1][2])<eps) tx=0,ty=f[2][3]/f[2][2];
		else ty=f[1][3]/f[1][2],tx=(f[2][3]-f[2][2]*ty)/f[2][1];
	}
	else if(abs(f[2][2])<eps)
	{
		if(abs(f[2][1])<eps) ty=0,tx=f[1][3]/f[1][1];
		else tx=f[2][3]/f[2][1],ty=(f[1][3]-f[1][1]*tx)/f[1][2];
	}
	else 
	{
		tt=f[2][1]/f[1][1];f[2][1]=0;
		f[2][2]-=tt*f[1][2];f[2][3]-=tt*f[1][3];
		ty=(abs(f[2][2])<eps)?0:f[2][3]/f[2][2];
		tx=(abs(f[1][1])<eps)?0:(f[1][3]-f[1][2]*ty)/f[1][1];
	}
	ans=abs(A*tx*tx+B*ty*ty+C*tx*ty+D*tx+E*ty+F);
	if(ans<eps) puts("0.00");
	else printf("%.2lf\n",ans);
}
int main()
{
	scanf("%d",&n);
	int op,p;
	while(n--)
	{
		scanf("%d",&op);
		if(!op)
		{
			scanf("%lf%lf%lf%lf",&x,&y,&xx,&yy);
			ins(); 
		}
		else if(op==1)
		{
			scanf("%d",&p);
			del(p);
		}
		else 
		{
			if(!ji){puts("0.00");continue;}
			sol();
		} 
	}
	return 0;
}

 

评论

还没有任何评论,你来说两句吧

发表评论

衫小寨 出品