Mr.MainandWindmills

Mr. Main took a train from city $s$ to city $t$ and passed a plain full of windmills. The train ran in a straight line. A windmill is a machine used for wind power generation. Its fan blades rotate when the wind blows. From his perspective, colorful windmills lined up on the horizon from left to right.

As the train was running, the order of windmills from his perspective was constantly changing: a windmill was originally on the left/right of another, and then changed to its right/left;

Given the coordinates of the windmills, please find the coordinate of him when he just observed the $h$ -th windmill exchanged order with other windmills for the $k$ -th times. It is guaranteed that any three of the points given, the cities and the windmills, were not collinear, and that all of the windmills were on the same side of the line that the train ran along.

As shown in the picture, in Mr. Mian's perspective, B was initially to the left of A, and later to the right of A.

The first line of input contains two integers $n$ and $m$ , where $n(1\leq n\leq 1000)$ is number of windmills, and $m(1\leq m\leq 10^4)$ is number of queries.

The second line contains four integers $x_s$ , $y_s$ , $x_t$ and $y_t$ ( $-10^6\leq x_s,y_s,x_t,y_t\leq 10^6$ ), which are the coordinates of the starting city s and destination city t.

The next $n$ lines describe the windmills, the $i$ -th of which contains two integers $x_i$ ,
$y_i$ ( $-10^6\leq x_i,y_i\leq 10^6$ ), which are the coordinates of the $i$ -th windmill.

The next $m$ lines describe the queries, the $i$ -th of which contains two integers, $h_i$ and $k_i$ ( $1\leq h_i\leq n,1\leq k_i\leq 10^6$ ), denoting a query for the coordinates when observing the $k_i$ -th pass of the $h_i$ -th windmill.

Output m lines, each containing two real numbers $x_i, y_i$ , representing the coordinates when the $h_i$ -th windmill is observed to exchange order with other windmills for k times; if it does not exist, output -1. Your answer is considered correct if its absolute or relative error with the standard answer is less than $10^{-5}$ .

#include<bits/stdc++.h> using namespace std; int n, m, h, k; double x[1234], y[1234], xs, ys, xt, yt, t; vector<double>ans[1234]; int main() { cin >> n >> m >> xs >> ys >> xt >> yt; for(int i = 0; i < n; i++) cin >> x[i] >> y[i]; for(int i = 0; i < n; i++) { for(int j = i + 1; j < n; j++) { t = ys*(x[i]-x[j]) + xs*(y[j]-y[i]) + x[j]*y[i] - x[i]*y[j]; t /= (xt-xs) * (y[i]-y[j]) + (yt-ys) * (x[j]-x[i]); if(t > 0 && t < 1) { ans[i].push_back(t); ans[j].push_back(t); } } sort(ans[i].begin(), ans[i].end()); } while(m--) { cin >> h >> k; if(ans[h-1].size() < k) puts("-1"); else { t = ans[h-1][k-1]; printf("%.6f %.6f\n", xs + t*(xt-xs), ys + t*(yt-ys)); } } }

详情