10382 - Watering Grass(욕심 구간 커버 문제) 수면 커버

double qiuzhi(int id)
{
    double t1=cc[id].rid*cc[id].rid;
    double t2=w*w/4;
    double t3=t1-t2;
    double t4=sqrt(t3);
    return t4;
}

void to_qujian()
{
    for(int i=0; i<t; i++)
    {
        double zhi=qiuzhi(i);
        qq[i].a=cc[i].pos-zhi;
        qq[i].b=cc[i].pos+zhi;
    }
}

전형적인 욕심 구간 커버 문제, 유여가 책에서 말했듯이 사고방식만 코드가 없다~ 그는 항상 이렇게 사람을 아프게 한다.
본 문제에 있어서 관건적인 것은 구체적인 문제에서'구간'으로 추상화하는 것이다~!원과 직사각형 변의 교점을 구간의 좌우 단점으로 삼아라!
두 가지 방법을 써서 책에 있는 방법에 따라 적당한 구간을 여러 번 캡처하는 방법으로 한 번 했는데 코드가 비교적 뚜렷하게 실현되었지만 시간이 초과되었다.
원인은 이미 명확하게 분석되었는데 0(n)의 복잡도인 줄 알았지만 정렬의 nlog(n)의 복잡도를 소홀히 하고 매번 순환할 때마다 정렬을 했다. 10000의 데이터 양이 시간을 초과한 것은 예상했던 일이다.

#include<cstdio>//       ~    ~~
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
using namespace std;
const int maxn=10000+10;
int n,t;
double l,w;
int flag1,flag2;

struct circle
{
    double pos;
    double rid;
} cc[maxn];
struct qujian
{
    double a;
    double b;
} qq[maxn];
void input(int n,double l,double w)
{
    t=0;
    int temp=n;
    for(int i=0; i<temp; i++)
    {
        double a1,b1;
        scanf("%lf%lf",&a1,&b1);
        if(b1<=w/2)
        {
            n--;
            continue;
        }
        else
        {
            cc[t].pos=a1;
            cc[t++].rid=b1;
        }
    }
}

bool cut_qujian(double left,double right)
{
    flag1=0;
    flag2=0;
    for(int i=0; i<t; i++)
    {
        if(qq[i].a<=left)
        {
            flag1=1;
            qq[i].a=left;
        }
        if(qq[i].b>=right-0.0000000001)
        {
            flag2=1;
            qq[i].b=right;
        }
    }
    if(flag1==1&&flag2==1)
        return true;
    else
        return false;
}
double qiuzhi(int id)
{
    double t1=cc[id].rid*cc[id].rid;
    double t2=w*w/4;
    double t3=t1-t2;
    double t4=sqrt(t3);
    return t4;
}

void to_qujian()
{
    for(int i=0; i<t; i++)
    {
        double zhi=qiuzhi(i);
        qq[i].a=cc[i].pos-zhi;
        qq[i].b=cc[i].pos+zhi;
    }
}


int cmp(qujian a,qujian b)
{
    if(a.a!=b.a) return a.a<b.a;
    else return a.b>b.b;
}

int main()
{
    while(scanf("%d%lf%lf",&n,&l,&w)!=EOF)
    {
        input(n,l,w);
        to_qujian();
        double left=0,right=l;
        int ans=-1;
        int cnt=0;
        while(cut_qujian(left,right))
        {
            cnt++;
            sort(qq,qq+t,cmp);
            left=qq[0].b;
            if(left>=right)
            {
                ans=1;
                break;
            }
        }
        if(ans==-1)
        {
            printf("-1
");
        }
        else
            printf("%d
",cnt);
    }
    return 0;
}

그리고 사고방식은 바꿀 수 없으니 실현하는 방식으로 바꾸자~
아래와 같은 0(n^2)처럼 보이지만 실제로는 복잡도가 0(n)인 방법을 써서 선배가 주신 것이 좋다고 생각합니다.

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
using namespace std;
const int maxn=10000+10;
int n,t;
double l,w;
int flag1,flag2;

struct circle
{
    double pos;
    double rid;
} cc[maxn];
struct qujian
{
    double a;
    double b;
} qq[maxn];
void input(int n,double l,double w)
{
    t=0;
    int temp=n;
    for(int i=0; i<temp; i++)
    {
        double a1,b1;
        scanf("%lf%lf",&a1,&b1);
        if(b1<=w/2)
        {
            n--;
            continue;
        }
        else
        {
            cc[t].pos=a1;
            cc[t++].rid=b1;
        }
    }
}
double qiuzhi(int id)
{
    double t1=cc[id].rid*cc[id].rid;
    double t2=w*w/4;
    double t3=t1-t2;
    double t4=sqrt(t3);
    return t4;
}

void to_qujian()
{
    for(int i=0; i<t; i++)
    {
        double zhi=qiuzhi(i);
        qq[i].a=cc[i].pos-zhi;
        qq[i].b=cc[i].pos+zhi;
    }
}


int cmp(qujian a,qujian b)
{
    return a.a<b.a;
}

int solve()
{
    int cnt=0;
    double right=0;
    for(int i=0; i<t; i++)
    {

        double nowr=right;
        for(; qq[i].a<=right; i++)
        {
            if(qq[i].b>nowr)
                nowr=qq[i].b;
        }
        if(nowr==right) return -1;
        right=nowr;
        cnt++;
        i--;
    }
    if(right<l) return -1;
    return cnt;
}
int main()
{
    while(scanf("%d%lf%lf",&n,&l,&w)!=EOF)
    {
        input(n,l,w);
        to_qujian();
        int ans;
        sort(qq,qq+t,cmp);
        ans=solve();
        if(ans==-1)
        {
            printf("-1
");
        }
        else
            printf("%d
",ans);
    }
    return 0;
}

오랜만에 이 문제를 푸는 듯한 느낌이 들어서 좋다.