#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdlib.h>

using namespace std;

typedef struct
{
    int x;
    int y;
}Island;

typedef struct
{
    float a;
    float b;
}Inst;//区间值，左端点为a,右端点为b

int num=0;
int visit[1000];//每个坐标对应的区间访问前为0,访问后为1
Inst m[1000];
float xio[1000]={0.0};

int cmp(const void *a,const void *b)
{
    return ((*(Inst *)a).a-(*(Inst *)b).a);
}

int solution(int n,float d,Island *is)
{
    num=1;
    if(n>=1&&n<=1000)
    {
        int i,j=0,index=0,cu=0;
        float dx,ma;
        if(d<=0)
        {
            num=-1;
            return 1;
        }
        for(i=0;i<n;i++)
        {
            if(is[i].y>d||is[i].y<0)
            {
                num=-1;
                return 1;
            }
        }
        for(i=0;i<n;i++)
        {
            dx=(float)pow((double)(d*d-is[i].y*is[i].y),0.5);
            m[i].a=is[i].x-dx;
            m[i].b=is[i].x+dx;
        }
        qsort(m,n,sizeof(Inst),cmp);
        for(i=0;i<n;i++)
        {
            visit[i]=0;
        }
        /*while(cu<n)//还有没遍历到的区间继续循环
        {
            xio[index]=m[cu].b;
            visit[cu]=1;
            num++;
            index++;
            while(xio[index-1]>=m[cu+1].a)
            {
                visit[cu+1]=1;
                if(xio[index-1]>m[cu+1].b)
                {
                    xio[--index]=m[cu+1].b;
                    index++;
                }
                cu++;
            }
            cu++;
            for(j=0;j<n;j++)//判断是否遍历完所有区间
            {
                if(visit[j]==0)
                {
                    cu=j;
                    break;
                }
            }
        }*/
        ma=m[0].b;
        for(i=1;i<n;i++)
        {
            if(m[i].a>ma)
            {
                num++;
                ma=m[i].b;
            }
            else if(m[i].b<ma)
            {
                ma=m[i].b;
            }
        }
        return 1;
    }
    else if(n==0&&d==0)
    {
        return 0;
    }
    else
    {
        num=-1;
        return 1;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    int n,d,i,index=1;
    Island is[1000];
    cin>>n;
    cin>>d;
    for(i=0;i<n;i++)
    {
        cin>>is[i].x;
        cin>>is[i].y;
    }
    while(solution(n,d,is))
    {
        cout<<"Case "<<index++<<": "<<num<<endl;
        cin>>n;
        cin>>d;
        for(i=0;i<n;i++)
        {
            cin>>is[i].x;
            cin>>is[i].y;
        }
    }
    return 0;
}

• Re:有无大佬帮忙看看这道题的代码为啥一直WA,poj1328 (2910) 335233577 2021-10-20 22:27:50