Mr. Mole has built some tunnels in his little manor. For convenience, you can regard one tunnel as a segment on 2d plane. One tunnel can be described by its two endpoint P1 = (x1, y1) and P2 = (x2, y2).
One day, Mr. Mole comes up with an interesting problem -- if he stands on the point (x, y), which tunnel is the nearest tunnel ?
Notice : the distance between one tunnel T and a point P is defined as dist(T, P) = minP'∈T dist(P', P), which means the distance is exactly the distance between P and the nearest point on the tunnel.
Only one test case.
The first line contains two integers n, m.
n denotes that there are n tunnels in Mr.Mole's manor.
m denotes that there are m queries from Mr. Mole.
In the following n lines, the (i+1)-th line contains information of the i-th tunnel. There are 4 integers x1, y1, x2, y2 in each line which denote a tunnel P1 (x1, y1) - P2 (x2, y2).
In the following m lines, there are 2 integers x, y in each line which denote a query point P(x, y).
Input data ensures that n ≤ 104, m ≤ 105 and all coordinates are betwee 0 and 216-1 .
The data is randomly generated. Feel free to try any method !
For every query point, output the nearest tunnel ID(starting from 1) in one line. If there are multiple options, output the minimum ID.
In the first query, tunnel 1 and tunnel 2 have the same distance from the query point. So we choose tunnel 1 as the output.
In the second query, the query point locates exactly on the tunnel 2. So 2 is the output.
In the third query, tunnel 3 has the minimum distance from the query point.
有
n
n
n条线段,
m
m
m次询问。每次询问包含一个点的坐标,然后要求输出距离这个点最近的直线的位置下标(即输入次序)。
注意所有数据均为随机数据,The data is randomly generated. Feel free to try any method !(来自题干)
首先,碰到数据随机的题目,我们一定要抓住随机这一个特点。随机也就代表着平均、分布均匀的意思。
对于这道题,数据的随机使得直线的分布很均匀。
感性的去想,对于某一个固定的点,距离他最近的直线一定不会离的很远,并且距离该点比较远的大部分直线我们都可以直接不去考虑。那么,我们就可以把一个
n
∗
n
n*n
n∗n的大矩形,分成
n
∗
n
\sqrt{n} * \sqrt{n}
n∗n 个
n
∗
n
\sqrt{n} * \sqrt{n}
n∗n的小矩形。我们用
(
x
,
y
)
(x,y)
(x,y)代表第
x
x
x行,第
y
y
y列的小矩形。如果某个点位于
(
x
,
y
)
(x,y)
(x,y)的小矩形中,那么,按照刚刚对随机数据的分析,我们可以假设,距离该点最近的线段一定会经过(不是起点或者终点在这个小矩形中)
(
x
,
y
)
,
(
x
,
y
−
1
)
,
(
x
,
y
+
1
)
,
(
x
−
1
,
y
−
1
)
,
(
x
−
1
,
y
)
(x,y),(x,y-1),(x,y+1),(x-1,y-1),(x-1,y)
(x,y),(x,y−1),(x,y+1),(x−1,y−1),(x−1,y)
(
x
−
1
,
y
+
1
)
,
(
x
+
1
,
y
−
1
)
,
(
x
+
1
,
y
)
,
(
x
+
1
,
y
+
1
)
(x-1,y+1),(x+1,y-1),(x+1,y),(x+1,y+1)
(x−1,y+1),(x+1,y−1),(x+1,y),(x+1,y+1)
这九个小矩形。因为数据随机,所以经过这9个小矩形的线段的数量不会很多(可以自行计算一下平均值),直接暴力求解于这些直线的最小值即可。
注意当直线的数量比较少的时候,很可能不会满足这个性质,所以在直线数目比较少的时候,我们可以直接暴力求解。
还有一个问题就是我们怎么知道每一条线段经过了哪些个矩形呢?易知每一条直线最多经过
n
\sqrt{n}
n个小矩形,对于每一条直线,我们可以让起点的
x
x
x坐标加上
n
\sqrt{n}
n,然后去计算相应的
y
y
y坐标。循环往复,知道标记完当前直线经过的所有格子。具体实现见代码。
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;
const int STEP = (1 << 8) + 1;
const double eps = 1e-12;
const int MAXN = 1e6 + 100, MAXV = STEP * STEP;
struct Point {
double x{}, y{};
Point() = default;
Point(double _x, double _y) {
x = _x;
y = _y;
}
Point operator-(const Point &b) const {
return {x - b.x, y - b.y};
}
Point operator+(const Point &b) const {
return {x + b.x, y + b.y};
}
Point operator/(const double &b) const {
return {x / b, y / b};
}
Point operator*(const double &b) const { return {x * b, y * b}; }
double operator^(const Point &b) const { return x * b.y - y * b.x; }
double operator*(const Point &b) const { return x * b.x + y * b.y; }
void input() { scanf("%lf %lf", &x, &y); }
double distance(Point p) {
return sqrt((x - p.x) * (x - p.x) + (y - p.y) * (y - p.y));
}
};
struct Line {
Point s, e;
Line() = default;
double length() { return s.distance(e); }
void input() {
s.input();
e.input();
}
} line[MAXN];
vector<int> v[MAXV];
int sgn(double x) {
if (fabs(x) < eps)return 0;
if (x < 0)return -1;
return 1;
}
//点到直线的距离
double pointToLineDis(Line l, Point p) {
return fabs((p - l.s) ^ (l.e - l.s)) / l.length();
}
//点到线段的距离
double pointToSegDis(Line l, Point p) {
if (sgn(l.length()) == 0)
return p.distance(l.s);
if (sgn((p - l.s) * (l.e - l.s)) < 0 || sgn((p - l.e) * (l.s - l.e)) < 0)
return min(p.distance(l.s), p.distance(l.e));
return pointToLineDis(l, p);
}
int getID(double x, double y) {
int tx = int(round(x)), ty = int(round(y));
return ((tx >> 8) * (1 << 8)) + (ty >> 8);
}
pair<double, int> getAns(Point tPoint, int ID) {
pair<double, int> ans = make_pair(1e18, 0);
double tDis;
for (auto tPos:v[ID]) {
tDis = pointToSegDis(line[tPos], tPoint);
if (sgn(ans.first - tDis) > 0) {
ans.first = tDis;
ans.second = tPos + 1;
} else if (sgn(ans.first - tDis) == 0 && ans.second > tPos + 1) {
ans.second = tPos + 1;
}
}
return ans;
}
void solve(double &ans, int &ansPos, Point tPoint, int tID) {
pair<double, int> tAns;
tAns = getAns(tPoint, tID);
if (sgn(ans - tAns.first) > 0)
ans = tAns.first, ansPos = tAns.second;
else if (sgn(ans - tAns.first) == 0 && ansPos > tAns.second)
ansPos = tAns.second;
}
int main() {
int n, m, tID, preID, ansPos, tempID;
scanf("%d %d", &n, &m);
Point tPoint, vec;
for (int i = 0; i < n; i++) {
line[i].input();
tPoint = line[i].s;
vec = line[i].e - line[i].s;
vec = vec / 256.0;
preID = -1;
for (int j = 0; j <= 256; j++) {
tPoint = line[i].s + vec * j;
tID = getID(tPoint.x, tPoint.y);
if (0 <= tID && tID < MAXV) {
if (preID != tID)
v[tID].push_back(i);
preID = tID;
} else
break;
}
}
double ans, tDis;
if (n <= 500) {
for (int i = 0; i < m; i++) {
ans = 1e18, ansPos = 0;
tPoint.input();
for (int j = 0; j < n; j++) {
tDis = pointToSegDis(line[j], tPoint);
if (ans > tDis) {
ans = tDis;
ansPos = j + 1;
}
}
printf("%d\n", ansPos);
}
return 0;
}
for (int i = 0; i < m; i++) {
ans = 1e18, ansPos = 0;
tPoint.input();
tID = getID(tPoint.x, tPoint.y);
solve(ans, ansPos, tPoint, tID);
tempID = tID + (1 << 8);
if (0 <= tempID && tempID < MAXV)
solve(ans, ansPos, tPoint, tempID);
tempID = tID + (1 << 8) + 1;
if (0 <= tempID && tempID < MAXV)
solve(ans, ansPos, tPoint, tempID);
tempID = tID + (1 << 8) - 1;
if (0 <= tempID && tempID < MAXV)
solve(ans, ansPos, tPoint, tempID);
tempID = tID - (1 << 8);
if (0 <= tempID && tempID < MAXV)
solve(ans, ansPos, tPoint, tempID);
tempID = tID - (1 << 8) + 1;
if (0 <= tempID && tempID < MAXV)
solve(ans, ansPos, tPoint, tempID);
tempID = tID - (1 << 8) - 1;
if (0 <= tempID && tempID < MAXV)
solve(ans, ansPos, tPoint, tempID);
tempID = tID + 1;
if (0 <= tempID && tempID < MAXV)
solve(ans, ansPos, tPoint, tempID);
tempID = tID - 1;
if (0 <= tempID && tempID < MAXV)
solve(ans, ansPos, tPoint, tempID);
printf("%d\n", ansPos);
}
return 0;
}