URAL 1111 Squares(求点到正方形的距离)

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;
}