比赛 |
20161223 |
评测结果 |
AAAAAAAAAAA |
题目名称 |
激光 |
最终得分 |
100 |
用户昵称 |
confoo |
运行时间 |
0.600 s |
代码语言 |
C++ |
内存使用 |
161.29 MiB |
提交时间 |
2016-12-23 19:48:09 |
显示代码纯文本
//sro FarmerJohn orz
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#include <map>
#include <vector>
#define file(x) "lasers." #x
using std::min;
const int N = 1e5 + 10, V = N << 2, INF = 0x3f3f3f3f, E = 1e7;
inline int zip(int u, int d) {return u*4 + d;}
int n, x[N], y[N], cor[N << 1], dis[V], xb, yb, ans;
std::vector<int> yp[N], xp[N];
int tmp[N];
struct EDGE{int u, v, w;}st[E];
int hed[V], nxt[E], sz;
void add(int u, int v, int w) {
st[++sz] = (EDGE){u, v, w};
nxt[sz] = hed[u], hed[u] =sz;
}
void lisan(int x[N], int& ls) {
ls = 0;
std::map<int, int> rk;
memcpy(tmp, x, sizeof(tmp));
std::sort(tmp + 1, tmp + 1 + n);
for (int i = 1; i <= n; i++) {
rk[tmp[i]] = ++ls;
while (i + 1 <= n && tmp[i + 1] == tmp[i]) ++i;
}
for (int i = 1; i <= n; i++) x[i] = rk[x[i]];
}
std::queue<int> q;
bool inq[V];
int posx[N], posy[N];
bool cmpx(int a, int b) {return x[a] < x[b];}
bool cmpy(int a, int b) {return y[a] < y[b];}
int main() {
freopen(file(in), "r", stdin);
freopen(file(out), "w", stdout);
scanf("%d", &n);
n += 2;
for (int i = 1; i <= n; i++) scanf("%d%d", &x[i], &y[i]);
lisan(x, xb), lisan(y, yb);
for (int i = 1; i <= n; i++) xp[x[i]].push_back(i), yp[y[i]].push_back(i);
for (int i = 1; i <= xb; i++) {
std::sort(xp[i].begin(), xp[i].end(), cmpy);
for (int j = 0; j < xp[i].size(); j++) posx[xp[i][j]] = j;
}
for (int i = 1; i <= yb; i++) {
std::sort(yp[i].begin(), yp[i].end(), cmpx);
for (int j = 0; j < yp[i].size(); j++) posy[yp[i][j]] = j;
}
for (int u = 1; u <= n; u++)
for(int d = 0; d < 4; d++) for (int dd = -1; dd <= 1; dd++) {
int nd = (d + dd + 4)%4, c = -1;
if (nd == 0) if(posx[u] + 1 < xp[x[u]].size()) c = xp[x[u]][posx[u] + 1];else;
else if (nd == 2) if(posx[u] - 1 >= 0) c = xp[x[u]][posx[u] - 1];else;
else if (nd == 1) if(posy[u] + 1 < yp[y[u]].size()) c = yp[y[u]][posy[u] + 1];else;
else if (nd == 3) if(posy[u] - 1 >= 0) c = yp[y[u]][posy[u] - 1];else;
if (c != -1) add(zip(u, d), zip(c, nd), dd != 0);
}
memset(dis, 0x3f, sizeof(dis));
for (int d = 0, u; d < 4; d++) dis[u = zip(1, d)] = 0, inq[u] = 1, q.push(u);
while (!q.empty()) {
int u = q.front();q.pop();
for (int e = hed[u], v; v = st[e].v; e = nxt[e]) if (dis[v] > dis[u] + st[e].w) {
dis[v] = dis[u] + st[e].w;
if (!inq[v]) inq[v] = 1, q.push(v);
}
inq[u] = 0;
}
int ans = INF;
for (int d = 0; d < 4; d++) ans = min(ans, dis[zip(2, d)]);
printf("%d", ans == INF ? -1 : ans);
}