zoj3862 intersection[2015浙大校赛C题]

题意：

按1-2n的编号给定2n个点以及n条线段，每个点属于且仅属于一条线段。

线段用端点的编号确定。

现在一次操作可以交换两个点的编号，

要求在不超过n+10次的操作后使得任意两条线段不相交。

输入保证任意两个点不重合，任意三个点不相交。

思路：

首先要明确，不是要求最少操作次数，只要不超过n+10次就可以。

所以一定有解：

step 1: 点配对

    把所有点按水平序排好，人为配对：排名2k-1的点和排名2k的点组成一条线段。(2k-1并不是点的编号，只是排序后的位置)

    这样的话没有线段会相交。

step 2: 统计操作次数

    点已经配好了，只要计算从原来的配对变成现在的配对需要多少次操作。

    假设排序后的点编号是：a, b, ... , c, ... , d , ....

    本来是a和c组成一条线段，b和d组成一条线段

    为了让a和c配对，交换b和c的编号（其实是交换b和c对应的点坐标。。。）

    显然最多进行n次操作

总之step 1比较简单，step 2我讲不清楚。。。

把握一点：操作之后，点的编号对应关系不变。

比如说1号点一开始与4号点组成线段，操作之后还是1号点和4号点组成线段

但是1号点和4号点的坐标可能和之前不一样

理解这一点就好了。。。

#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 200000;
int a[N+10], rk[N+10], f[N+10];
int ansx[N+10], ansy[N+10];
int n;
struct point{
    int x, y, id;
    void input(){
        scanf("%d %d", &x, &y);
    }
}p[N+10];
bool cmp(point a, point b){
    if (a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}
int main(){
    int test;
    scanf("%d", &test);
    while (test--){
        scanf("%d", &n);
        for (int i=1; i<=2*n; i++){
            p[i].input();
            p[i].id = i;
        }
        int a, b;
        for (int i=1; i<=n; i++){
            scanf("%d %d", &a, &b);
            f[a] = b; f[b] = a;
        }
        int nn = 2*n;
        sort(p+1, p+n*2+1, cmp);
        for (int i=1; i<=nn; i++)
            rk[p[i].id] = i;
        int cnt = 0;
        for (int i=1; i<=nn; i+=2){
            int a = p[i].id, b = p[i+1].id;
            if (f[a] != b){
                int c = f[a], d = f[b];
                cnt++;
                ansx[cnt] = b; ansy[cnt] = c;
                swap(p[i+1].id, p[rk[c]].id);
                swap(rk[b], rk[c]);
            }
        }
        printf("%d\n", cnt);
        for (int i=1; i<=cnt; i++)
            printf("%d %d\n", ansx[i], ansy[i]);
    }
    return 0;
}

zoj3862 intersection[2015浙大校赛C题]

原文：http://blog.csdn.net/hccz95/article/details/45029791