由于跟另外一題基本一樣，這里不多解釋了，請參閱：
http://www.shnenglu.com/hoolee/archive/2012/08/13/187069.html以下是本題代碼：
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define LEN 10100
typedef struct
{
double l;
double r;
}Node;
typedef struct
{
int x0;
int y0;
int x1;
int y1;
}Line;
Line lin[LEN];
Node nd[LEN];
long long count;
int cmp(const void *a, const void *b)
{
Node *a0 = (Node*)a;
Node *b0 = (Node*)b;
if(fabs(a0 -> l - b0 -> l) > 0.000000001)
return a0 -> l > b0 -> l ? 1 : -1;
else
return a0 -> r > b0 -> r ? 1 : -1;
}
void Merge(Node *nd, int f, int m, int r)
{
int i, j, k;
Node *b = (Node*)malloc(sizeof(Node) * (r - f + 3));
i = f;
j = m + 1;
k = 0;
while(i <= m && j <= r)//merge
{
if(nd[i].r <= nd[j].r)
{
b[k++] = nd[i++];
if(k + f > i)
count += k + f - i;
}
else
b[k++] = nd[j++];
}
while(i <= m)
{
b[k++] = nd[i++];
if(k + f > i)
count += k + f - i;
}
while(j <= r)
b[k++] = nd[j++];
for(i = f; i <= r; i++)//copy
nd[i] = b[i - f];
free(b);
}
void MgSort(Node *nd, int f, int r)
{
if(f < r)
{
int m = (f + r) / 2;
MgSort(nd, f, m);
MgSort(nd, m + 1, r);
Merge(nd, f, m, r);
}
}
int main()
{
int i, j;
int n;
double x0, y0, x1, y1;
double k, t;
double l, r;
while(scanf("%d", &n) != EOF)
{
for(i = 0; i < n; i++)
{
scanf("%d%d%d%d", &lin[i].x0, &lin[i].y0, &lin[i].x1, &lin[i].y1);
}
scanf("%lf%lf", &l, &r);
for(i = 0; i < n; i++)
{
k = 1.0 * (lin[i].y1 - lin[i].y0) / (lin[i].x1 - lin[i].x0);
nd[i].l = k * (l - lin[i].x0) + lin[i].y0;
nd[i].r = k * (r - lin[i].x0) + lin[i].y0;
}
qsort(nd, n, sizeof(Node), cmp);
count = 0;
MgSort(nd, 0, n - 1);
printf("%lld\n", count);
}
//system("pause");
}
posted on 2012-08-13 15:12
小鼠標 閱讀(255)
評論(0) 編輯 收藏 引用 所屬分類:
排序 、
暑期培訓周賽