神棍節献礼之——URAL 1111 Squares(幾何学)
問題はN個の正方形があり、各正方形は対角線の2つの頂点座標を与え、指定点までの距離の大きさ関係を判断し、距離が近いから遠いまで、これらの正方形の番号を昇順に出力することを意味する.
なお、正方形のエッジは座標軸と平行ではない可能性があります.また、指定点が正方形の内部にある場合は、距離は0とみなされます.
方法は,対角線の2点座標から残りの2点を算出し,指定点からこの正方形(凸四角形)までの距離,すなわち点から線分までの距離を算出し,最小値をとることが明らかである.
コード:
なお、正方形のエッジは座標軸と平行ではない可能性があります.また、指定点が正方形の内部にある場合は、距離は0とみなされます.
方法は,対角線の2点座標から残りの2点を算出し,指定点からこの正方形(凸四角形)までの距離,すなわち点から線分までの距離を算出し,最小値をとることが明らかである.
コード:
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 51;
const double MAX = 1e8;
const double eps = 1e-14;
struct point{
double x,y;
};
struct square{
point p1,p2;
int id;
double dist;
}s[N];
int dcmp(double x){
if (x < -eps) return -1;
else return x > eps;
}
int cmp(square a,square b){
if(dcmp(a.dist-b.dist)==0)return a.id < b.id;
return dcmp(a.dist - b.dist)<0;
}
double min(double a,double b){
if(dcmp(a-b)==1)return b;
return a;
}
double max(double a,double b){
if(dcmp(a-b)==1)return a;
return b;
}
double dis(point a,point b){
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double crossProduct(point a,point b,point c){// ac ab
return (c.x - a.x)*(b.y - a.y) - (b.x - a.x)*(c.y - a.y);
}
int pin_convexh(point a,point p[]){// a
int n=4;
p[n] = p[0]; p[n+1] = p[1];
for(int i=0; i<n; i++)
if( dcmp(crossProduct(p[i],p[i+1],a)*crossProduct(p[i+1],p[i+2],a))==-1 )
return 0;
return 1;
}
double jobs(point p,point l1,point l2){// p l1l2
point t = p;
t.x += l1.y - l2.y; t.y += l2.x - l1.x;
if( dcmp( crossProduct(l1,t,p)*crossProduct(l2,t,p) ) != -1 ) //
return dcmp(dis(p,l1)-dis(p,l2))==-1 ? dis(p,l1) : dis(p,l2);
return fabs( crossProduct(p,l1,l2) )/dis(l1,l2);
}
point Whirl(double cosl, double sinl, point a, point b){// ab a A,b->b1,sinl sinA
b.x -= a.x; b.y -= a.y;
point c;
c.x = b.x * cosl - b.y * sinl + a.x;
c.y = b.x * sinl + b.y * cosl + a.y;
return c;
}
double fun(point cent,square ss){
point p[10],mid;
mid.x=(ss.p1.x+ss.p2.x)/2.0; mid.y=(ss.p1.y+ss.p2.y)/2.0;
p[0]=ss.p1;
p[1]=Whirl(0,1,mid,p[0]);
p[2]=ss.p2;
p[3]=Whirl(0,1,mid,p[2]);
if(pin_convexh(cent,p)==1)return 0.0;
else {
double min_dist=MAX;
for(int i=0;i<4;i++)
min_dist=min(jobs(cent,p[i],p[i+1]),min_dist);
return min_dist;
}
}
int main()
{
point cent;
int n,i;
double a,b,c,d;
while(~scanf("%d",&n)){
for(i=1;i<=n;i++){
scanf("%lf%lf%lf%lf",&s[i].p1.x,&s[i].p1.y,&s[i].p2.x,&s[i].p2.y);
s[i].id=i;
}
scanf("%lf%lf",¢.x,¢.y);
for(i=1;i<=n;i++)s[i].dist=fun(cent,s[i]);
sort(s+1,s+n+1,cmp);
printf("%d",s[1].id);
for(i=2;i<=n;i++)printf(" %d",s[i].id);
puts("");
}
return 0;
}