pku3462 Lucky Light (简单题)

题目:

杭电5月1号的热身赛H题,题目意思是说给定一个光源和若干条线段,这样线段会在X轴上投影,使得X轴上有些部分是暗的,有些是亮的,求其中亮的块数...

直观的想法,先求出所有线段在X轴上的投影,对阴影按X坐标排序,如果两个阴影不相交,亮的块数加1...

由于排序函数的错误,贡献了7次WA....看了NH的代码才找出错误....(注意注释部分)

我的代码:

 

 

#include<iostream>
using namespace std;

const double eps=1e-8;

struct CPoint
{double x,y;};

struct CLine
{
    CPoint start,end;
};
/*int cmp(const void *a,const void *b)//错误的排序
{
    CLine *c=(CLine *)a;
    CLine *d=(CLine *)b;
    return c->start.x-d->start.x;//这里有可能是double型...
}*/
int cmp(const void*a,const void*b){
    return ((struct CLine *)a)->start.x-((struct CLine*)b)->start.x>0?1:-1;
}
int dcmp(double x)
{
    if(x<-eps) return -1;
    else return (x>eps);
}

double cross(CPoint p0,CPoint p1,CPoint p2)
{
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}

int LineIntersection(CPoint p1,CPoint p2,CPoint p3,CPoint p4,CPoint &cp)
{
    double u=cross(p1,p2,p3),v=cross(p2,p1,p4);
    if(dcmp(u+v))
    {
        cp.x=(p3.x*v+p4.x*u)/(v+u);
        cp.y=(p3.y*v+p4.y*u)/(v+u);
        return 1;
    }
    if(dcmp(u)) return 0;
    if(dcmp(cross(p3,p4,p1))) return 0;
    return -1;
}

int main()
{
    int n,i,test,count;
    CLine X,line[105],shadow[105],pass;
    CPoint light,cp,temp;
    cin>>test;
    X.start.x=-100000;
    X.start.y=0;
    X.end.x=100000;
    X.end.y=0;
    while(test--)
    {
        cin>>n;count=2;
        cin>>light.x>>light.y;
        for(i=0;i<n;i++)
        {
            cin>>line[i].start.x>>line[i].start.y>>line[i].end.x>>line[i].end.y;
        }
        if(n==0) {cout<<1<<endl;continue;}
        for(i=0;i<n;i++)
        {
            LineIntersection(X.start,X.end,line[i].start,light,cp);
            shadow[i].start=cp;
            LineIntersection(X.start,X.end,line[i].end,light,cp);
            shadow[i].end=cp;
            if(shadow[i].start.x>shadow[i].end.x)
            {
                temp=shadow[i].start;
                shadow[i].start=shadow[i].end;
                shadow[i].end=temp;
            }
        }
        qsort(shadow,n,sizeof(shadow[0]),cmp);
        pass=shadow[0];
        for(i=1;i<n;i++)
        {
            if(shadow[i].start.x>=pass.start.x&&shadow[i].start.x<=pass.end.x)
            {
                if(dcmp(shadow[i].end.x-pass.end.x)==1)
                    pass.end=shadow[i].end;
            }
            else
            {
                count++;
                pass=shadow[i];
            }
        }
        cout<<count<<endl;
    }
    return 0;
}
/*
3
90 90
10 0 20 0
15 0 40 0
35 0 45 0
*/

NH的代码:

#include<stdio.h>
#include<stdlib.h>

struct A{
    double start;
    double end;
};

int compare(const void*a,const void*b){
    return ((struct A*)a)->start-((struct A*)b)->start>0?1:-1;
}

int main()
{
    struct A segs[100];
    int test,n,a,b,x1,y1,x2,y2,i,j,result;
    double t,end;

    scanf("%d",&test);
    while(test--){
        scanf("%d",&n);
        scanf("%d%d",&a,&b);
        result=1;
        
        for(i=0;i<n;++i){
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            segs[i].start=(double)(b*x1-a*y1)/(b-y1);
            segs[i].end=(double)(b*x2-a*y2)/(b-y2);
            if(segs[i].start>segs[i].end){
                t=segs[i].start;
                segs[i].start=segs[i].end;
                segs[i].end=t;
            }
        }
        qsort(segs,n,sizeof(segs[0]),compare);
        end=-99999;
        for(i=0;i<n;i++){
            if(segs[i].start>end)
                result++;
            if(segs[i].end>end)
                end=segs[i].end;
        }
        printf("%d\n",result);
    }
    return 0;
}