題意描述：
求若干條線段交叉點(diǎn)的個(gè)數(shù)。題目保證不會(huì)有兩條以上的線段交與一點(diǎn)。
乍一看還以為是計(jì)算幾何的東西，其實(shí)不然，題目的條件限制使得這一題很簡(jiǎn)單。我們把題目描述的地圖想象為笛卡爾坐標(biāo)系上的點(diǎn)，可以規(guī)定，兩邊岸上的點(diǎn)都有相同的x值（分別為x0，x1且x0<x1），這樣，如果x0，x1所夾范圍內(nèi)存在相交的兩條線段l1、l2的話，假設(shè)他們與x0，x1交點(diǎn)的y值分別為l1y0,l1y1和l2y0,l2y1，那么這兩條線段必須滿足以下簡(jiǎn)單條件：(l1y0-l2y0)*(l1y1-l2y1)<0。也就是說(shuō)，在直線x0上和x1上，l1、l2的y值大小順序是相反的，這讓我們聯(lián)想到了逆序?qū)Α?br />具體做法是：
先將每條線段按x0對(duì)應(yīng)的y值排序（我稱之為第一次排序），然后根據(jù)x1對(duì)應(yīng)的y值求出逆序?qū)Φ膫€(gè)數(shù)，既是交叉點(diǎn)的個(gè)數(shù)。求逆序?qū)Φ姆椒ㄗ钪苯拥木褪窃诿芭菖判蚴怯涗浗粨Q的次數(shù)，不過(guò)這樣會(huì)超時(shí)，改進(jìn)的算法是利用歸并排序，在每次歸并的時(shí)候統(tǒng)計(jì)逆序?qū)€(gè)數(shù)（注意兩個(gè)數(shù)相等的情況，當(dāng)兩數(shù)相等時(shí)它們不是逆序?qū)?/strong>）。
注意：在第一次排序中，因?yàn)椴煌€段的y值可能是相等的，這種情況下我們要依據(jù)x1對(duì)應(yīng)的y值排序。忽略這種情況會(huì)導(dǎo)致計(jì)算的逆序?qū)€(gè)數(shù)增多。
逆序?qū)㈤啠?a href="http://www.shnenglu.com/hoolee/archive/2012/07/18/184090.html">http://www.shnenglu.com/hoolee/archive/2012/07/18/184090.html
做的好艱辛，感謝冰冰學(xué)長(zhǎng)。
以下是本題代碼：
#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
小鼠標(biāo) 閱讀(1318)
評(píng)論(1) 編輯 收藏 引用 所屬分類:
排序