usaco_5_2_2_fence3.cpp

usaco自己做的1到5章的代码

/*
PROB: fence3 
LANG: C++
*/
/*
这道题考察计算几何知识。
看过题很容易想到直接枚举点到个线段的距离，因为电源的范围是[0,100]的区间内的，而且只有一位小数
可以考虑枚举0~1000的，然后除以10。不过这样是k*n^2的，n=1000，k=150，这样很明显会超时。
那么可以这么考虑，我们先不管小数，直接枚举整数点，这样可以找到到各条线段距离最短的整数点(mx,my)，
然后以这个整数点为中心的周围面积为4的矩形((mx-1,my-1)和(mx+1,my+1)为对角线的矩形)就是要枚举的范围了，
每次递增0.1，再算出最小的距离，这样不会超时，不过效率也不是很高，后几组数都是0.5s左右了。
*/
#include<iostream>
#include<fstream>
#include<memory>
#include<cmath>
#include<algorithm>
#include<iomanip>
//#define cin fin
using namespace std;
/* 常用的常量定义 */
const double INF = 1E200;   
const double EP = 1E-10;
const int MAXV = 300; 
const double PI = 3.14159265;
/* 基本几何结构 */
struct POINT
{
	double x;	
	double y;	POINT(double a=0, double b=0) { x=a; y=b;}		//constructor
};
struct LINESEG
{
	POINT s;
	POINT e;	LINESEG(POINT a, POINT b) { s=a; e=b;}	
				LINESEG() { }	
};
LINESEG lines[152];
POINT pt;
int n,m,minn,mx,my;
double dissum,minsum;
double dist(POINT p1,POINT p2)                // 返回两点之间欧氏距离
{
	return( sqrt( (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y) ) );	
}
bool equal_point(POINT p1,POINT p2)           // 判断两个点是否重合 
{
	return ( (abs(p1.x-p2.x)<EP)&&(abs(p1.y-p2.y)<EP) );
}
double dotmultiply(POINT p1,POINT p2,POINT p0)
{
	return ((p1.x-p0.x)*(p2.x-p0.x)+(p1.y-p0.y)*(p2.y-p0.y));
}

double relation(POINT p,LINESEG l)
{
	LINESEG tl;
	tl.s=l.s;
	tl.e=p;
	return dotmultiply(tl.e,l.e,l.s)/(dist(l.s,l.e)*dist(l.s,l.e));
}
POINT perpendicular(POINT p,LINESEG l)
{
	double r=relation(p,l);
	POINT tp;
	tp.x=l.s.x+r*(l.e.x-l.s.x);
	tp.y=l.s.y+r*(l.e.y-l.s.y);
	return tp;
}

double ptolinesegdist(POINT p,LINESEG l,POINT &np)
{
	double r=relation(p,l);
	if(equal_point(l.s,l.e)) return dist(p,l.s);   //线段l的两端点相等时特殊处理
	if(r<0)
	{
		np=l.s;
		return dist(p,l.s);
	}
	if(r>1)
	{
		np=l.e;
		return dist(p,l.e);
	}
	np=perpendicular(p,l);
	return dist(p,np);
}

int main()
{
	ifstream fin("fence3.in");
	ofstream fout("fence3.out");
    int i,j,k,des;
	POINT a,b;
    fin>>n;
	for(i=0;i<n;i++)
	{
		fin>>lines[i].s.x>>lines[i].s.y>>lines[i].e.x>>lines[i].e.y;
	}
	minsum=999999;
	for(i=0;i<=100;i++)
		for(j=0;j<=100;j++){
			dissum=0;
			a.x=i;
			a.y=j;
			for(k=0;k<n;k++)
				dissum+=ptolinesegdist(a,lines[k],b);
			if(dissum<minsum) {minsum=dissum; mx=i;my=j;}
		}
	double sx=mx*10;
	double sy=my*10;
	for(i=(mx-1)*10;i<(mx+1)*10;i++)
		for(j=(my-1)*10;j<(my+1)*10;j++)
		{
			if(i<0) {i=0;continue;}
			if(j<0) {j=0;continue;}
			double x=i*1.0/10;
			double y=j*1.0/10;
			a.x=x; a.y=y;
			dissum=0;
			for(k=0;k<n;k++)
				dissum+=ptolinesegdist(a,lines[k],b);
			if(dissum<minsum) {minsum=dissum; sx=i*1.0;sy=j*1.0;}
		}
		fout<<setiosflags(ios::fixed)<<setprecision(1)<<sx/10<<' '<<sy/10<<' '<<minsum<<endl;
    return 0;
}