zoj 3157
这个代码交上去是错的，但是我找了好长时间都没有找到，所以请求大神帮忙啊！
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
int sum;
struct fun{
double x,y;
}t[10010];
double b[5005],c[5005];
int cmp(const void *a , const void *b )
{
struct fun *c = (struct fun *)a;
struct fun *d = (struct fun *)b;
if(fabs(c->x-d->x)>0.00000001) return c->x>d->x?1:-1;
else return c->y>d->y?1:-1;
}
void fenzhi(struct fun *t,int p,int r)
{
int q=0,i,k,j,m,n;
if(r-p>0)
{ q=(p+r)/2;
fenzhi(t,p,q);
fenzhi(t,q+1,r);
}
if(r>p)
{
for(i=p;i<=q;i++)
b[i-p]=t[i].y;
m=i-1;
for(i=0;i<r-q;i++)
c[i]=t[i+q+1].y;
n=i-1;
for(k=0,i=0,j=0;i<=m&&j<=n;k++)
{
if(c[j]-b[i]>0.000000001)
{
t[k].y=b[i];
i++;
}
else
{
t[k].y=c[j];
sum=sum+m-i+1;
j++;
}
}
while(i<=m)
{
t[k].y=b[i];
k++;i++;
}
while(j<=n)
{
t[k].y=c[j];
k++;j++;
}
}
}
int main()
{
int w,i;
double q[10005][4],n,m,l,r;
while(scanf("%d",&w)!=EOF)
{
for(i=0;i<w;i++)
scanf("%lf %lf %lf %lf",&q[i][0],&q[i][1],&q[i][2],&q[i][3]);
scanf("%lf %lf",&l,&r);
for(i=0;i<w;i++)
{
n=(q[i][3]-q[i][1])/(q[i][2]-q[i][0]);
m=q[i][3]-n*q[i][2];
t[i].x=n*l+m;
t[i].y=n*r+m;
}
qsort(t,w,sizeof(t[0]),cmp);
sum=0;
fenzhi(t,0,w-1);
printf("%d\n",sum);
}
return 0;
}
[解决办法]
[code=C/C++][/code]#include<stdio.h>
#include<math.h>
#include<stdlib.h>
int sum;
struct fun{
double x,y;
}t[10010];
double b[5005],c[5005];
int cmp(const void *a , const void *b )
{
struct fun *c = (struct fun *)a;
struct fun *d = (struct fun *)b;
if(fabs(c->x-d->x)>0.00000001) return c->x>d->x?1:-1;
else return c->y>d->y?1:-1;
}
void fenzhi(struct fun *t,int p,int r)
{
int q=0,i,k,j,m,n;
if(r-p>0)
{ q=(p+r)/2;
fenzhi(t,p,q);
fenzhi(t,q+1,r);
}
if(r>p)
{
for(i=p;i<=q;i++)
b[i-p]=t[i].y;
m=i-1;
for(i=0;i<r-q;i++)
c[i]=t[i+q+1].y;
n=i-1;
for(k=0,i=0,j=0;i<=m&&j<=n;k++)
{
if(c[j]-b[i]>0.000000001)
{
t[k].y=b[i];
i++;
}
else
{
t[k].y=c[j];
sum=sum+m-i+1;
j++;
}
}
while(i<=m)
{
t[k].y=b[i];
k++;i++;
}
while(j<=n)
{
t[k].y=c[j];
k++;j++;
}
}
}
int main()
{
int w,i;
double q[10005][4],n,m,l,r;
while(scanf("%d",&w)!=EOF)
{
for(i=0;i<w;i++)
scanf("%lf %lf %lf %lf",&q[i][0],&q[i][1],&q[i][2],&q[i][3]);
scanf("%lf %lf",&l,&r);
for(i=0;i<w;i++)
{
n=(q[i][3]-q[i][1])/(q[i][2]-q[i][0]);
m=q[i][3]-n*q[i][2];
t[i].x=n*l+m;
t[i].y=n*r+m;
}
qsort(t,w,sizeof(t[0]),cmp);
sum=0;
fenzhi(t,0,w-1);
printf("%d\n",sum);
}
return 0;
}
