CGL_1_A: Projection | 李博的博客
0%

CGL_1_A: Projection

Projection

For given three points p1,p2,p, find the projection point x of p onto p1p2.

Input

1
2
3
4
5
6
xp1 yp1 xp2 yp2
q
xp0 yp0
xp1 yp1
...
xpq−1 ypq−1

In the first line, integer coordinates of p1 and p2 are given. Then, q queries are given for integer coordinates of p.

Output

For each query, print the coordinate of the projection point x. The output values should be in a decimal fraction with an error less than 0.00000001.

Constraints

  • 1≤q≤1000
  • −10000≤xi,yi≤10000
  • p1 and p2 are not identical.

Sample Input 1

1
2
3
4
5
0 0 2 0
3
-1 1
0 1
1 1

Sample Output 1

1
2
3
-1.0000000000 0.0000000000
0.0000000000 0.0000000000
1.0000000000 0.0000000000

Sample Input 2

1
2
3
0 0 3 4
1
2 5

Sample Output 2

1
3.1200000000 4.1600000000

Source: https://onlinejudge.u-aizu.ac.jp/problems/CGL_1_A

计算几何模版题,求一个点在一个直线上的投影。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<iostream>
#include<cmath>
#include<iomanip>
using namespace std;
struct Point{
double x,y;
Point(){}
Point(double x,double y):x(x),y(y){}
};
typedef Point Vector;
Vector operator + (Vector A,Vector 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);
}
Vector operator / (Vector A,double p){
return Vector(A.x/p,A.y/p);
}
bool operator < (const Point& a,const Point& b){
return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
const double eps = 1e-10;
int dcmp(double x){
if(fabs(x)<eps) return 0; else return (x<0?-1:1);
}
bool operator == (const Point& a,const Point& b){
return dcmp(a.x-b.x)==0 && dcmp(a.y-b.y)==0;
}
//点积
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 Angle(Vector A,Vector B){
return acos(Dot(A,B)/Length(A)/Length(B));
}

//叉积
double Cross(Vector A,Vector B){
return (A.x*B.y-A.y*B.x);
}
//三角形面积的二倍的叉乘公式
double Area2(Point A,Point B,Point C){
return Cross(B-A,C-A);
}
//向量旋转,rad是弧度
Vector Rotate(Vector A,double rad){
return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));
}
//计算向量的单位法线,先逆时针旋转90度,然后把长度归一化
Vector Normal(Vector A){
double Len=Length(A);
return Vector(-A.y/Len,A.x/Len);
}
//求两直线交点
//调用前请确保P+tv和Q+tw有唯一交点,当且仅当Cross(v,w)非0
Point GetLineIntersection(Point P,Vector v,Point Q,Vector w){
Vector u=P-Q;
double t=Cross(w,u)/Cross(v,w);
return P+v*t;
}
//点到直线的距离
double DistanceToLine(Point P,Point A,Point B){
Vector v1=B-A,v2=P-A;
return fabs(Cross(v1,v2))/Length(v1);
}
//点到线段的距离
double DistanceToSegment(Point P,Point A,Point B){
if(A==B) return Length(P-A);
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);
}
//点在直线上的投影
Point GetLineProjection(Point P,Point A,Point B){
Vector v=B-A;
return A+v*(Dot(v,P-A)/Dot(v,v));
}
int main(){
Point A,B;
cin>>A.x>>A.y>>B.x>>B.y;
int t;
cin>>t;
while(t--){
Point P;
cin>>P.x>>P.y;
cout<<fixed<<setprecision(10)<<GetLineProjection(P,A,B).x<<" "<<GetLineProjection(P,A,B).y<<endl;
}
return 0;
}
如果对您有帮助,请我喝杯奶茶?