Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM-ICPC竞赛训练》暑期课面向全球招生。容量有限,报名从速!

将点排序,每次接着前面的往后找就行了,可是WA了一页,改成两层循环就过了。。。

Posted by AK47biubiubiu at 2017-01-10 09:40:43 on Problem 2318
我的思路是直接将点排序,因为题目说线段是有序的,每次找点只需再上一次的基础上往下找就行了,怎么会错呢?
struct line
{
    double x1,y1,x2,y2;
} a[N],b[N];
int v[N];
int cmp(line a,line b)
{
    return a.x1<b.x1;
}
double multi(line b,line a)
{
    return (a.x1-b.x1)*(a.y2-b.y1)-(a.x2-b.x1)*(a.y1-b.y1);
}
int main()
{
    int n,m;
    double x1,y1,x2,y2;
    while(~scanf("%d",&n)&&n)
    {
        scanf("%d%lf%lf%lf%lf",&m,&x1,&y1,&x2,&y2);
        memset(v,0,sizeof(v));
        for(int i=1; i<=n; i++) //n条分界分成n+1个区域
        {
            scanf("%lf%lf",&a[i].x1,&a[i].x2);
            a[i].y1=y1;
            a[i].y2=y2;
        }
        a[0].x1=x1,a[0].y1=y1,a[0].x2=x1,a[0].y2=y2;//开始隔板
        a[n+1].x1=x2,a[n+1].y1=y1,a[n+1].x2=x2,a[n+1].y2=y2;//最后一块区域
        for(int i=0; i<m; i++) scanf("%lf%lf",&b[i].x1,&b[i].y1);
        sort(b,b+m,cmp);
        int j=0;
        for(int i=0; i<m; i++)
        {
//            while(multi(b[i],a[j])>0&&j<=n+1) j++;
//             j--;//用while一直WA,而改成下面的循环就过了。。
            for(j=0; j<=n+1; j++)
                if(multi(b[i],a[j])<0)
                {
                    j--;
                    break;
                }
            v[j]++;
        }
        for(int i=0; i<=n; i++)
            printf("%d: %d\n",i,v[i]);
        printf("\n");
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator