[Wc2012]memory
题目描述
江苏省常州高级中学是一所百年名校，这里萦绕着无数人难以忘怀的回忆。 Will 记得，在他小的时候，常州高级中学改建以前，学校里有一片高大的水杉林，每到水杉落叶之时，针状的叶子会像毯子一样盖在地上，走在上面浪漫而又闲适。那时，Will 和同学们还喜欢用这些针叶，在水杉树下，玩“取叶子”的游戏。 游戏一开始，大家先将 n片针叶平铺在地上。接着，每一轮可以有一个同学选择一片针叶，按水平或者垂直方向将针叶移走（也就是平移到无穷远处）——当然，前提是移动过程中不被任何尚未移走的针叶所阻碍。如果某一轮针叶的移动会被阻碍，那么这次移动就是非法的，是不被允许的。n轮过后，当针叶都被 移走时，游戏也就结束了。 针叶并不是任何时刻都可以被移动的。当针叶很多的时候，判断每一轮中一片针叶是否可以按一个特定的方向移动是一件很麻烦的事情。 现在我们将地面抽象为平面直角坐标系，n 片针叶抽象为平面上 n 条互不相交的线段，并将其从 1到n编号，Will 还将给出每一轮游戏中，他想要移动的针叶编号以及移动方向，请你帮助他：
- 找出最早的一次非法移动出现在哪一轮；
- 给出一个合法的移动方案完成这个游戏。 注意：在线段移动时仅端点接触不会造成阻碍，具体请参见样例。
输入格式
第一行包含一个正整数n，表示针叶的数量。 接下来 n行，每行 4个整数，描述针叶的位置信息。其中第 i 行的整数为 ai，bi，ci，di，表示编号为 i 的针叶所抽象成的线段的端点为(ai, bi)和(ci, di)。 接下来 n 行，每行 2 个整数，描述移动操作。其中第 i 行的整数为 pi，qi，表示第 i 轮移动的针叶编号为 pi，方向为 qi。其中 qi为一个 0 到 3 之间的整数，0 表示向左平移（即 x 轴负方向） ，1 表示向上平移（即 y 轴正方向） ，2 表示向右平移，3表示向下平移。 输入数据保证： 所有线段长度为正，两两之间没有公共点，且不存在垂直或者水平的线 段; p1到pn恰好组成一个1到 n的排列； Will 所给出的移动操作中一定存在非法移动； n轮均合法的移动操作总是存在的。
输出格式
一共包含n + 1行。 输出的第一行包含一个1到n之间的整数，表示最早出现非法移动的是哪一轮。 接下来 n行，每行两个整数，内容同输入格式所述，描述一个合法的移动序列。
5
2 5 5 8
2 1 3 5
5 2 6 5
7 0 4 2
3 1 4 0
2 0
3 0
4 0
1 2
5 1
3
2 0
3 0
4 3
1 2
5 1
提示
在 Will 给出的移动方案的第 3轮中，编号为 4的针叶向左移动会被编号为 5 的针叶阻碍。
题目来源
鸣谢 PTY
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <set>
#include <cmath>
#include <stack>
#define REP(i, x, y) for (int i = x, _ = y; i <= _; i ++)
#define rep(i, x, y) for (int i = x, _ = y; i >= _; i --)
#define MSET(a, x) memset(a, x, sizeof(a))
#define CLEAR(a) MSET(a, 0)
#define lc (o << 1)
#define rc (o << 1|1)
template <typename T> bool Chkmin(T &x, T y) { return x > y? x = y, true : false; }
template <typename T> bool Chkmax(T &x, T y) { return x < y? x = y, true : false; }
const int MAXN = 100000 + 1000, oo = 0x3f3f3f3f;
const double eps = 1e-8;
int n, nowx, cntx, cnty;
struct Line{
int x1, y1, x2, y2, id;
Line() {}
Line(int x1, int y1, int x2, int y2, int id): x1(x1), y1(y1), x2(x2), y2(y2), id(id) {}
double Gety(int x) const
{
return y1 + 1.0 * (y2 - y1) / (x2 - x1) * 1.0 * (x - x1);
}
bool operator < (const Line &a) const{
return Gety(nowx) - a.Gety(nowx) < -eps;
}
}line[MAXN];
struct SegmentTree{
int minv[MAXN * 8], mv[MAXN * 8];
void Init()
{
MSET(mv, 0x3f);
MSET(minv, 0x3f);
}
void Update(int o, int x)
{
Chkmin(minv[o], x);
Chkmin(mv[o], x);
}
void Pushdown(int o)
{
if (mv[o] != oo) {
Update(lc, mv[o]);
Update(rc, mv[o]);
mv[o] = oo;
}
}
void Pushup(int o)
{
minv[o] = std::min(minv[lc], minv[rc]);
}
void modify(int o, int l, int r, int L, int R, int X)
{
if (L <= l && r <= R) {
Update(o, X);
return ;
}
int mid = (l + r) >> 1;
Pushdown(o);
if (L < mid)
modify(lc, l, mid, L, R, X);
if (mid < R)
modify(rc, mid, r, L, R, X);
Pushup(o);
}
int query(int o, int l, int r, int L, int R)
{
int mid = (l + r) >> 1, minx = oo;
if (L <= l && r <= R)
return minv[o];
Pushdown(o);
// Don't forget this 'pushdown()'!
if (L < mid)
Chkmin(minx, query(lc, l, mid, L, R));
if (mid < R)
Chkmin(minx, query(rc, mid, r, L, R));
return minx;
}
void Modify(int l, int r, int x)
{
modify(1, 1, cntx, l, r, x);
}
int Query(int l, int r)
{
return query(1, 1, cntx, l, r);
}
} t;
int sx[MAXN * 2], sy[MAXN * 2];
void Discrete()
{
int cnt = 0;
REP (i, 1, n) {
sx[cnt ++] = line[i].x1;
sx[cnt ++] = line[i].x2;
}
std::sort(sx, sx + cnt);
cntx = std::unique(sx, sx + cnt) - sx;
}
struct Scan{
int x, flag, id;
Scan() {}
Scan(int x, int flag, int id): x(x), flag(flag), id(id) {}
bool operator < (const Scan &a) const {
return x != a.x? x < a.x : flag < a.flag;
}
};
std::vector<Scan> scan;
std::vector<int> G[MAXN];
std::set<Line> s;
int in[MAXN], order[MAXN], rank[MAXN],dir[MAXN];
void GetDAG()
{
int flag, id, x1, x2, cnt = 0;
scan.clear();
s.clear();
REP (i, 1, n) {
G[i].clear();
in[i] = 0;
x1 = line[i].x1;
x2 = line[i].x2;
scan.push_back(Scan(x1, 1, i));
scan.push_back(Scan(x1, 2, i));
scan.push_back(Scan(x2, 2, i));
scan.push_back(Scan(x2, 3, i));
}
std::sort(scan.begin(), scan.end());
for (int i = 0; i < scan.size(); i ++) {
std::set<Line>::iterator p1, p2;
flag = scan[i].flag;
id = scan[i].id;
nowx = scan[i].x;
switch (flag) {
case 1:
s.insert(line[id]);
break;
case 2:
p1 = p2 = s.find(line[id]);
p2 ++;
if (p1 != s.begin()) {
p1 --;
G[id].push_back(p1->id);
in[p1->id] ++;
}
if (p2 != s.end()) {
G[p2->id].push_back(id);
in[id] ++;
}
break;
case 3:
s.erase(line[id]);
break;
}
}
}
void TopSort()
{
int u, v, cnt = 0;
std::stack<int> st;
REP (i, 1, n)
if (in[i] == 0)
st.push(i);
while (!st.empty()) {
u = st.top();
st.pop();
order[++ cnt] = u;
rank[u] = cnt;
for (int i = 0; i < G[u].size(); i ++) {
in[v = G[u][i]] --;
if (!in[v])
st.push(v);
}
}
}
int put[MAXN];
void Task1()
{
int ans = oo, x1, x2, y1, y2, tmp, u, j = 0;
do {
j = (j + 1) % 4;
Discrete();
GetDAG();
TopSort();
t.Init();
tmp = n + 1;
for (int i = n; i >= 1; i --) {
u = put[i];
x1 = std::lower_bound(sx, sx + cntx, line[u].x1) - sx + 1;
x2 = std::lower_bound(sx, sx + cntx, line[u].x2) - sx + 1;
if (dir[u] == j && t.Query(x1, x2) < rank[u])
tmp = i;
t.Modify(x1, x2, rank[u]);
}
Chkmin(ans, tmp);
// Rotate
REP (i, 1, n) {
x1 = -line[i].y1, x2 = -line[i].y2;
y1 = line[i].x1, y2 = line[i].x2;
if (x1 > x2) {
std::swap(x1, x2);
std::swap(y1, y2);
}
line[i] = Line(x1, y1, x2, y2, line[i].id);
}
} while (j);
printf("%d\n", ans);
}
void Task2()
{
Discrete();
GetDAG();
TopSort();
REP (i, 1, n)
printf("%d %d\n", order[i], 1);
}
void Solve()
{
Task1();
Task2();
}
void Init()
{
int x1, y1, x2, y2, id, d;
scanf("%d", &n);
REP (i, 1, n) {
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
if (x1 > x2) {
std::swap(x1, x2);
std::swap(y1, y2);
}
line[i] = Line(x1, y1, x2, y2, i);
}
REP (i, 1, n) {
scanf("%d %d", &id, &d);
put[i] = id;
dir[id] = d;
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("2584.in", "r", stdin);
freopen("2584.out", "w", stdout);
#endif
Init();
Solve();
#ifndef ONLINE_JUDGE
fclose(stdin);
fclose(stdout);
#endif
return 0;
}