題意描述：
求若干條線段交叉點的個數。題目保證不會有兩條以上的線段交與一點。
乍一看還以為是計算幾何的東西，其實不然，題目的條件限制使得這一題很簡單。我們把題目描述的地圖想象為笛卡爾坐標系上的點，可以規定，兩邊岸上的點都有相同的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.shnenglu.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
小鼠標 閱讀(1336)
評論(1) 編輯 收藏 引用 所屬分類:
排序