URAL 1111 Squares(求点到正方形的距离)
题意:
给你一个点P和n个正方形(不一定平行坐标轴),要你求这个点P到每个正方形的最小距离且按距离从小到大输出正方形的编号. 如果点P在某个正方形内部,那么距离为0. 每个正方形仅给出一条对角线的两个顶点.
分析:
首先根据正方形的一条对角线旋转90度,然后用中点加上(或减去)旋转后向量的一半可以得到正方形的另外两个点.
然后判断该正方形是否包含了点P,如果没有包含,那么点P到正方形的距离就是P点到正方形4条线段的距离了.
之后对所有正方形按距离从小到大(相同距离就按编号从小到大)做一次排序即可.
模板用的刘汝佳<<训练指南>>上的.
AC代码:
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const double eps=1e-14;
const double PI=acos(-1.0);
int dcmp(double x)
{
if(fabs(x)<eps) return 0;
return x<0?-1:1;
}
struct Point
{
double x,y;
Point(){}
Point(double x,double y):x(x),y(y){}
};
typedef Point Vector;
bool operator==(Point A,Point B)
{
return dcmp(A.x-B.x)==0&&dcmp(A.y-B.y)==0;
}
Vector operator-(Point A,Point B)
{
return Vector(A.x-B.x,A.y-B.y);
}
Vector operator+(Vector A,Vector B)
{
return Vector(A.x+B.x,A.y+B.y);
}
Vector operator*(Vector A,double p)
{
return Vector(A.x*p,A.y*p);
}
double Dot(Vector A,Vector B)
{
return A.x*B.x+A.y*B.y;
}
double Length(Vector A)
{
return sqrt(Dot(A,A));
}
double Cross(Vector A,Vector B)
{
return A.x*B.y-A.y*B.x;
}
Vector Rotate(Vector A,double rad)
{
return Vector(A.x*cos(rad)-A.y*sin(rad), A.x*sin(rad)+A.y*cos(rad));
}
bool InSegment(Point P,Point A,Point B)
{
return dcmp(Cross(A-P,B-P))==0 && dcmp(Dot(A-P,B-P))<=0;
}
bool PointInPolygon(Point p,Point *poly,int n)
{
int wn=0;
for(int i=0;i<n;++i)
{
if(InSegment(p,poly[i],poly[(i+1)%n]) ) return true;
int k=dcmp( Cross(poly[(i+1)%n]-poly[i], p-poly[i]) );
int d1=dcmp( poly[i].y-p.y );
int d2=dcmp( poly[(i+1)%n].y-p.y );
if(k>0 && d1<=0 && d2>0) wn++;
if(k<0 && d2<=0 && d1>0) wn--;
}
if(wn!=0) return true;
return false;
}
double DistanceToSegment(Point P,Point A,Point B)
{
if(A==B) return Length(A-P);
Vector v1=B-A,v2=P-A,v3=P-B;
if( dcmp(Dot(v1,v2))<0 ) return Length(v2);
else if( dcmp(Dot(v1,v3))>0 ) return Length(v3);
else return fabs(Cross(v1,v2))/Length(v1);
}
/***刘汝佳模板***/
const int maxn=50+5;
struct Square
{
Point p[4];
int id;
double dist;
bool operator<(const Square& rhs)const
{
return dist<rhs.dist || (dcmp(dist-rhs.dist)==0 && id<rhs.id);
}
}sq[maxn];
Point P;
int main()
{
int n;
while(scanf("%d",&n)==1)
{
for(int i=0;i<n;++i)
{
Point p[4];
scanf("%lf%lf%lf%lf",&p[0].x,&p[0].y,&p[2].x,&p[2].y);
Point mid=Point( (p[0].x+p[2].x)/2, (p[0].y+p[2].y)/2 );//中点
Vector v=Rotate(p[0]-p[2],PI/2)*0.5;//旋转后的对角线向量
p[1]=mid+v;//点+向量位移==点
p[3]=mid-v;//点+向量位移==点
for(int j=0;j<4;j++)sq[i].p[j]=p[j];
sq[i].dist=0;
sq[i].id=i+1;
}
scanf("%lf%lf",&P.x,&P.y);
for(int i=0;i<n;++i)//计算P点到每个正方形的距离
{
if(PointInPolygon(P,sq[i].p,4)) sq[i].dist=0;
else
{
double min_dist=1e8;
for(int j=0;j<4;++j)
min_dist = min(min_dist, DistanceToSegment(P,sq[i].p[j],sq[i].p[(j+1)%4]) );
sq[i].dist=min_dist;
}
}
sort(sq,sq+n);
printf("%d",sq[0].id);
for(int i=1;i<n;++i) printf(" %d",sq[i].id);
printf("\n");
}
return 0;
}
分享到:
相关推荐
Ural解题思路 Ural解题思路 Ural解题思路 Ural解题思路
Ural
URAL3D
Pascal acm_timus_ural_1148.pas
URAL(Timus Online Judge)部分测试数据 不全
Ural 1238 源代码 涉及算法(动态规划、贪心、DFS)
包含了ural题库中Vol_I 到Vol_III的所有题目的解题思路
Pascal acm_timus_ural_1099.pas
ural 题解 yuhch123。 关于yuhch123: ioi2008 金牌第一名,这是当初它做ural 第一卷时的题解
部分题解 大牛出品 Vol1-3 不是很全,约有200题左右
URAL-PHA
Ural ACM 1000源代码(c++),vc++6.0在XPsp2下编译通过,Timus Online Judge再线测评通过
因为大三了 不弄ACM了 所以这些就删了 删之前希望可以帮到别人
大量线段树题目 zoj 1610 线段覆盖 poj 2777 线段覆盖 poj 2528 需要离散化,建树不同,需要处理不同->注意这组数据 3 1 10 1 3 6 10 the ans ...zoj 2301 和上一题差不多,但是这个染色染的是点,注意染色为空的状况
资源分类:Python库 所属语言:Python 资源全名:ural-0.28.0.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
基于张量类模板的线性代数C ++库,可用于表示等级0的张量,标量向量,1的向量,2的矩阵,3的等级3的张量等。它还包括BLAS和LAPACK子例程的接口。
乌拉尔
28. The Theoretical Background of the Ural-Altale Hypothesis The hypothesis of common origin of the Altaic languages,and even the Ural-Altaic languages,dates from the first half of the last century....
Philip_Dural_UX-UI_Designer:UXUI设计器配置文件
资源分类:Python库 所属语言:Python 资源全名:ural-0.25.0-py3-none-any.whl 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059