2021 ICPC 昆明 I Mr Main and Windmills(直线与线段的交点)

2021 ICPC 昆明 I Mr. Main and Windmills(直线与线段的交点)

I Mr. Main and Windmills

大意：给出一条线段 ， 一个人从线段的起点走到线段的终点 ， 线段的一侧有若干风车 ， 当前的人在线段上的每一个位置观察风车都会得到一个顺序 。多次询问第 i 号风车被观察的位置第k次改变时人在线段上的位置。

思路：不难发现 ， 两个风车交换位置当且仅当人走过 两风车所在直线与线段交点的时候 ， 两两枚举风车求直线与线段交点 ， 然后根据和起始点的距离排序后根据要求输出即可。

易错点：这里线段与直线求交会有一个易错点。

如果先求 线段所在直线与风车直线的交点(line_make_point) ， 然后再判断交点是否在线段上(point_on_segment) ， 这样误差会巨大。因为直线求交会有除法 ， 求出的交点存在误差 ，然后判断点在线段上时会用到叉积 ， 叉积的几何意义就是形成三角形的面积 ， 如果线段特别特别长 ， 叉积就会很大 ， 从而在这里产生错误。

if(!line_make_point(l , r , now)) continue;
if(!point_on_segment(now , st , ed)) continue;
1
2

解决方法：

1. 对于求交问题 ， 先判断在求交

对应在这里 ， 就可以先判断线段和直线是否相交(toleft) ， 相交求交点即可 ， 这样是不会有判断误差的产生的。

if(toleft(st , p[i] , p[j]) * toleft(ed , p[i] , p[j]) > 0) continue;
line_make_point(l , r , now);
1
2

2. double 换成 long double ， 容限(eps) 调大即可

这里推荐第一种 ， 第一种更规范

#include
using namespace std;
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define int long long
const int N = 1e3 + 10;
const int mod = 1e9 + 7;
typedef pair<int,int>PII;

//--------------------------------------------------------------
const double eps = 1e-9;
const double pi = acos(-1);
inline double sqr(double x) {return x * x;} //平方
int sign(double x){
	if(fabs(x) < eps) return 0;
	if(x > 0) return 1;
	return -1;
}//符号
struct point{
	double x , y;
	point(){}
	point(double a , double b) : x(a) , y(b){}
	friend point operator + (const point &a , const point &b){
		return point(a.x + b.x , a.y + b.y);
	}
	friend point operator - (const point &a , const point &b){
		return point(a.x - b.x , a.y - b.y);
	}
	friend bool operator == (const point &a , const point &b){
		return !sign(a.x - b.x) && !sign(a.y - b.y);
	}
	friend point operator * (const point &a , const double &b){
		return point(a.x * b , a.y * b);
	}
	friend point operator * (const double &a , const point &b){
		return point(a * b.x , a * b.y);
	}
	friend point operator / (const point &a , const double &b){
		return point(a.x / b , a.y / b);
	}
	//向量模长 
	double norm(){ 
		return sqrt(sqr(x) + sqr(y));
	}
}; 

struct line{
	point a , b;
	line(){}
	line(point x , point y) : a(x) , b(y) {}
};

double det(const point &a , const point &b){
	return a.x * b.y - a.y * b.x;
}//叉积 判断两点共线 

double dot(const point &a , const point &b){
	return a.x * b.x + a.y * b.y;
}//点积

double dist(const point &a , const point &b){
	return (a - b).norm();
}//两点距离
 
point rotate_point(const point &a , const point &p , double A){
	double tx = p.x - a.x , ty = p.y - a.y;
	return point(a.x + tx * cos(A) - ty * sin(A) , a.y + tx * sin(A) + ty * cos(A));
}// p 点 绕 a 点逆时针旋转 A 弧度

int toleft(const point &p , const point &a , const point &b) {
	return sign(det(b - a , p - a));
	// 1 左 0 上 -1 右
}//只适用凸多边形

//判断点 p 是否在线段 st 上(包括端点)
bool point_on_segment(point p , point s , point t){
	return sign(det(p - s , t - s)) == 0 && sign(dot(p - s , p - t)) <= 0;
}

bool parallel(line a , line b){
	return !sign(det(a.a - a.b , b.a - b.b));
}

bool line_make_point(line a , line b , point &res){
	if(parallel(a , b)) return 0;
	double s1 = det(a.a - b.a , b.b - b.a);
	double s2 = det(a.b - b.a , b.b - b.a);
	res = (s1 * a.b - s2 * a.a) / (s1 - s2);
	return 1;
}
//--------------------------------------------------------------
//--------------------------------------------------------------

int n , m;
point st , ed , p[N] , now;
double x , y;
int h , k;

vector<tuple<double , double , double>>ans[N];

signed main(){

	IOS
	cout << fixed << setprecision(10);
	cin >> n >> m;
	
	cin >> x >> y;
	st = point{x , y};
	cin >> x >> y;
	ed = point{x , y};
	
	for(int i = 1 ; i <= n ; i ++){
		cin >> x >> y;
		p[i] = point{x , y};
	}
	
	line l = line{st , ed};
	
	for(int i = 1 ; i <= n ; i ++){
		for(int j = i + 1 ; j <= n ; j ++){
			line r = line{p[i] , p[j]};
			if(toleft(st , p[i] , p[j]) * toleft(ed , p[i] , p[j]) > 0) continue;
			line_make_point(l , r , now);
			ans[i].emplace_back(now.x , now.y , dist(now , st));
			ans[j].emplace_back(now.x , now.y , dist(now , st));
		} 
	}
	
	for(int i = 1 ; i <= n ; i ++) sort(ans[i].begin() , ans[i].end() , 
		[&](tuple<double , double , double> a , tuple<double , double , double> b){
			return get<2>(a) < get<2>(b);
		}
	);
	
	for(int i = 1 ; i <= m ; i ++){
		cin >> h >> k;
		if(ans[h].size() < k){
			cout << "-1\n";
		}else{
			auto [x , y , z] = ans[h][k - 1];
			cout << x << " " << y << "\n";
		}
	}
	
	return 0;
}
//freopen("文件名.in","r",stdin);
//freopen("文件名.out","w",stdout);
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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149