题意描述：
求若干条线段交叉点的个数。题目保证不会有两条以上的线段交与一点。
乍一看还以为是计算几何的东西，其实不然，题目的条件限制使得这一题很简单。我们把题目描述的地图想象为笛卡尔坐标系上的点，可以规定，两边岸上的点都有相同的x值（分别为x0，x1且x0<x1），这样，如果x0，x1所夹范围内存在相交的两条线段l1、l2的话，假设他们与x0，x1交点的y值分别为l1y0,l1y1和l2y0,l2y1，那么这两条线段必须满足以下简单条件：(l1y0-l2y0)*(l1y1-l2y1)<0。也就是说，在直线x0上和x1上，l1、l2的y值大小顺序是相反的，这让我们联想到了逆序对。
具体做法是：
先将每条线段按x0对应的y值排序（我称之为第一次排序），然后根据x1对应的y值求出逆序对的个数，既是交叉点的个数。求逆序对的方法最直接的就是在冒泡排序是记录交换的次数，不过这样会超时，改进的算法是利用归并排序，在每次归并的时候统计逆序对个数（注意两个数相等的情况，当
两数相等时它们不是逆序对）。
注意：在第一次排序中，
因为不同线段的y值可能是相等的，这种情况下我们要依据x1对应的y值排序。忽略这种情况会导致计算的逆序对个数增多。逆序对参阅：
http://www.cppblog.com/hoolee/archive/2012/07/18/184090.html做的好艰辛，感谢冰冰学长。
以下是本题代码：
#include<stdio.h>
#include<stdlib.h>
#define LEN 1010000
typedef struct
{
int e;
int w;
}Road;
long long count;
Road rd[LEN];
int cmp(const void *a, const void *b)
{
Road *a0 = (Road*)a;
Road *b0 = (Road*)b;
if(a0 -> e != b0 -> e)
return a0 -> e > b0 -> e ? 1 : -1;
else
return a0 -> w > b0 -> w ? 1 : -1;
}
void Merge(Road *rd, int f, int m, int r)
{
int i, j;
Road *b = (Road*)malloc(sizeof(Road) * (r - f + 3));
i = f;
j = m + 1;
int k = 0;
while(i <= m && j <= r)
{
if(rd[i].w > rd[j].w)
b[k++] = rd[j++];
else
{
b[k++] = rd[i++];
if(k + f > i)
count += (k + f - i);
}
}
while(i <= m)
{
b[k++] = rd[i++];
if(k + f > i)
count += (k + f - i);
}
while(j <= r)
b[k++] = rd[j++];
for(i = f; i <= r; i++)
rd[i] = b[i - f];
free(b);
}
void MgSort(Road *rd, int f, int r)
{
if(f < r)
{
int m = (f + r) / 2;
MgSort(rd, f, m);
MgSort(rd, m + 1, r);
Merge(rd, f, m, r);
}
}
int main()
{
int i, j, k;
int N, M, K;
int T;
scanf("%d", &T);
for(k = 1; k <= T; k++)
{
scanf("%d%d%d", &N, &M, &K);
for(i = 0; i < K; i++)
scanf("%d%d", &rd[i].e, &rd[i].w);
qsort(rd, K, sizeof(Road), cmp);
count = 0;
MgSort(rd, 0, K - 1);
printf("Test case %d: %lld\n", k, count);
}
//system("pause");
return 0;
}
posted on 2012-08-13 15:04
小鼠标 阅读(1297)
评论(1) 编辑 收藏 引用 所属分类:
排序