2021ICPC昆明站I-Mr. Main and Windmills

57 阅读 0 评论 38 点赞

我是靠谱客的博主热情大米，最近开发中收集的这篇文章主要介绍2021ICPC昆明站I-Mr. Main and Windmills，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接

题意：有n个点，位于x线段line(s,t)的一侧，记一点x，问x从s点到t点的过程中，以x点为观测点恰好第h个点与其他点第k次交换相对位置的时x的位置。

改变相对位置：以x点引一射线，a,b两点存在相对左右关系，若x点不变，改变射线相对位置仍不会改变，当x点移动到某处时，a,b两点的相对左右关系发生变化

约束条件:不存在两点与线段line(s,t)共线的情况

解析：关键之处在于找出a,b两点之间相对左右关系恰好发生改变的位置，容易想到该点为line(a,b)与线段line(s,t)的交点，不明白的话不妨自己画张图观察x点位于交点两侧时a,b的相对位置关系。

实现：n<=1000,所以我们可以处理出任意两点所构成的直线与线段line(s,t)的交点，然后按从s到t的顺序排序交点，询问第k次时，如果存在k个交点，则直接输出，否则无答案，总体时间复杂度约为O(n^2)

注意点：
①注意斜率不存在的情况
②精度，变量类型多为double，不过数据好像有些水，我没去管精度过了（我贴的代码也偷了个懒，没改）

AcCode

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<cstring>
#include<string>
#include<cmath>
#include<iomanip>

#define inf 0x3f3f3f3f

const int N = 1e3 + 100;

class point {
public:
	point();
	point(double x,double y);
	double getK(const point& t);
	double getx();
	double gety();
private:
	double x;
	double y;
}wind[N];

point::point() {};

point::point(double x, double y) { this->x = x, this->y = y; }

double point::getK(const point& t) {
	if (t.x != x) return (y - t.y) / (x - t.x);
	return inf;
}

double point::getx() { return x; }

double point::gety() { return y; }

double k=inf;
point st, ed;
double remK[N][N];
int flag;
std::vector<point>vec[N];

point getPoint(double tk,point tp) {//求交点
	if (k != inf) {
		double x = (k * st.getx() - tk * tp.getx() + tp.gety() - st.gety()) / (k - tk);
		double y = k * (x - st.getx()) + st.gety();
		return point(x, y);
	}
	else if (tk == inf) {
		double y = k * (tp.getx() - st.getx()) + st.gety();
		return point(tp.getx(), y);
	}
	else {
		double y = tk * (st.getx() - tp.getx()) + tp.gety();
		return point(st.getx(), y);
	}
}

bool check(point fir, point sec, point test) {//判断是否在线段st上
	double minx = std::min(fir.getx(), sec.getx());
	double maxx = std::max(fir.getx(), sec.getx());
	double miny = std::min(fir.gety(), sec.gety());
	double maxy = std::max(fir.gety(), sec.gety());
	double x = test.getx();
	double y = test.gety();
	if (x > maxx || x<minx || y>maxy || y < miny) return false;
	return true;
}

bool cmp(point a, point b) {//根据s，t的相对位置排序
	if (flag == 1) return a.getx() < b.getx();
	else if (flag == 2) return a.getx() > b.getx();
	else if (flag == 3) return a.gety() < b.gety();
	return a.gety() > b.gety();
}

signed main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	std::cout.setf(std::ios::fixed | std::ios_base::showpoint);
	std::cout.precision(10);
	int n, m;
	std::cin >> n >> m;
	double stx, sty, edx, edy;
	std::cin >> stx >> sty >> edx >> edy;
	st = point(stx, sty);
	ed = point(edx, edy);
	if (stx != edx) k = (edy - sty) / (edx - stx);
	for (int i = 1,x,y; i <= n; i++) {
		std::cin >> x >> y;
		wind[i] = point(x, y);
	}
	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			remK[i][j] = remK[j][j] = wind[i].getK(wind[j]);
			if (remK[i][j] == inf && k == inf) continue;
			point temp = getPoint(remK[i][j], wind[i]);
			if (check(st, ed, temp)) {
				vec[i].push_back(temp);
				vec[j].push_back(temp);
			}
		}
	}
	if (stx < edx) flag = 1;
	else if (stx > edx) flag = 2;
	else if (sty < edy) flag = 3;
	else flag = 4;
	for (int i = 1; i <= n; i++) sort(vec[i].begin(), vec[i].end(), cmp);
	while (m--) {
		int h, k;
		std::cin >> h >> k;
		if (k > vec[h].size()) std::cout << -1 << std::endl;
		else std::cout << vec[h][k - 1].getx() << " " << vec[h][k - 1].gety() << std::endl;
	}
}