大连网站 设计公司,做三方网站多少钱,网络策略,广告资源网2021 ICPC 昆明 I Mr. Main and Windmills(直线与线段的交点)
I Mr. Main and Windmills
大意#xff1a;给出一条线段 #xff0c; 一个人从线段的起点走到线段的终点 #xff0c; 线段的一侧有若干风车 #xff0c; 当前的人在线段上的每一个位置观察风车都会得到一个顺…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) 调大即可
这里推荐第一种 第一种更规范
#includebits/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 pairint,intPII;//--------------------------------------------------------------
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;vectortupledouble , double , doubleans[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() , [](tupledouble , double , double a , tupledouble , double , double b){return get2(a) get2(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);
