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. 对于求交问题 ， 先判断在求交

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

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

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

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

#include<bits/stdc++.h>
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(){IOScout << 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);