Poj Solution 1981

http://poj.org/problem?id=1981

#include<iostream>
#include"math.h"
#include"algorithm"
using namespace std;

struct point
{
    double x,y;
}p[310];

double jl(point i,point j)
{
    return sqrt((i.x-j.x)*(i.x-j.x)+(i.y-j.y)*(i.y-j.y));
}



bool fzk(point a,point b,double &in,double &out)
{
    double jiao,l,x;
    if((l=jl(a,b))>2)return 0;

    jiao=atan2(b.y-a.y,b.x-a.x);

    x=acos(l/2);

    in=jiao-x;
    out=jiao+x;
    
    return 1;
}

int n,m;
struct node
{
    char sign;
    double jiao;
}t[310];

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


void doit()
{
    int i,j,answer,now,kh;
    double a,b;
        
    answer=1;

    for(i=0;i<n;i++)
    {
        m=0;
        for(j=0;j<n;j++)
        {
            if(i!=j&&fzk(p[i],p[j],a,b))
            {
                t[m].jiao=a;t[m].sign=1;m++;
                t[m].jiao=b;t[m].sign=2;m++;
            }
        }

        std::sort(&t[0],&t[m],cmp);

        now=1;kh=9999;
    //    for(j=0;j<m&&t[j].sign==2;j++)
    //        ;
        if(m)
        for(j=0;j<m+kh;j++)
        {
            if(kh==9999&&t[j%m].sign==2)kh=j+1;
            if(t[j%m].sign==1)now++;
            else now--;
            if(now==0)while(1)
                cout<<"error";

            if(now>answer)answer=now;
        }

    }

    cout<<answer<<endl;
}

int main()
{
    int i;
    while(1)
    {
        cin>>n;
        if(n==0)break;
        for(i=0;i<n;i++)
            cin>>p[i].x>>p[i].y;

        doit();
    }

    return 0;
}


    
											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *