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

【好吧,再不求助会死人的】实在找不出问题所在了,WA了N次,能找到的测试数据都过了

Posted by 10112040 at 2013-07-28 15:57:47 on Problem 1328
代码如下,帮忙看一下,用的贪心的思路

#include <iostream>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<stdio.h>
using namespace std;
struct node
{
    double head,tail;
}a[1005];
int cmp(const void *a,const void *b)
{
    return (*(node *)a).tail>(*(node *)b).tail?1:-1;
}

int main()
{
    //freopen("in.txt","r",stdin);
    int n,d;
    char s[100];
    int c=1;
    while(cin>>n>>d,n||d)
    {
        memset(a,0,sizeof(a));
        int num=1;
        int i;
        int x,y;
        int flag=0;
        double temp;
        for(i=0;i<n;i++)
        {
            cin>>x>>y;
            if(y>d||d<0) flag=1;
            temp=sqrt((double)d*d-y*y);
            a[i].head=(double)x-temp;
            a[i].tail=(double)x+temp;
        }
        gets(s);
        if(flag)
        {
            cout<<"Case "<<c<<": "<<"-1"<<endl;
            c++;
            continue;
        }
        qsort(a,n,sizeof(node),cmp);
        int h=a[0].head,t=a[0].tail;
        for(i=1;i<n;i++)
        {
            if(a[i].head<=t)
            {
                if(a[i].tail<t)
                {
                    h=a[i].head;
                    t=a[i].tail;
                }
            }
            else
            {
                h=a[i].head;
                t=a[i].tail;
                num++;
            }
        }

        cout<<"Case "<<c<<": "<<num<<endl;
        c++;
    }

    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