"When no more circles can be inscribed, the distance between the first and the last inscribed circles is measured."

What is the definition of the distance between two circles?

kakoi v etoi zada4i moget bit` podvoh?
u menya na 12 teste valitsa

thanks...
sorry for my bad english

helo!
this is just a suggestion, i believe there should be an option (if they wish) for authors to display their email address to be contacted !
as it will enable and allow for more communications between authors.

my address is, baiguzair@gmail[dot]com

#include <iostream>
#include <cmath>
using namespace std;
int main(){
double PI=acos(-1.0);
int N; double r(0), perimeter(0);
cin>>N>>r;
double *pointx, *pointy;
pointx = new double[N+1];
pointy = new double[N+1];
for(int a=0; a<N; a++){
cin>>pointx[a]>>pointy[a];
}
pointy[N]= pointy[0];
pointx[N] = pointx[0];
cout.setf(ios::fixed);
cout.setf(ios::showpoint);
cout.precision(2);
if(N==1){
perimeter=2*PI*r;
cout<<perimeter;

}
else{
if(N==2){
perimeter=2*(pow((pow((pointx[0]-pointx[1]),2)+pow((pointy[0]-pointy[1]),2)),0.5)) + 2*PI*r;
cout<<perimeter;

}
else{
double angle(0);
for(int a=0; a<N; a++){
perimeter += pow((pow((pointx[a]-pointx[a+1]),2)+pow((pointy[a]-pointy[a+1]),2)),0.5);
}

double p1x, p2x, p3x, p1y, p2y, p3y, m1, m2;

p1x=pointx[N-1]; p2x=pointx[0]; p3x=pointx[1];
p1y=pointy[N-1]; p2y=pointy[0]; p3y=pointy[1];
if(p3x==p2x)
m1=tan(PI/2.0);
if(p2x==p1x)
m2=tan(PI/2.0);
if(p2x!=p3x)
m1=(p3y-p2y)/(p3x-p2x);
if(p2x!=p1x)
m2=(p1y-p2y)/(p1x-p2x);
angle = 2*PI - (PI + fabs(atan(m1)-atan(m2)));
for(int a=1; a<N; a++){
p1x=pointx[a-1]; p2x=pointx[a]; p3x=pointx[a+1];
p1y=pointy[a-1]; p2y=pointy[a]; p3y=pointy[a+1];
if(p3x==p2x)
m1=tan(PI/2.0);
if(p2x==p1x)
m2=tan(PI/2.0);
if(p2x!=p3x)
m1=(p3y-p2y)/(p3x-p2x);
if(p2x!=p1x)
m2=(p1y-p2y)/(p1x-p2x);

angle += ((2*PI) - (PI + fabs(atan(m1)-atan(m2))));
}

perimeter += r*angle;
cout<<perimeter;
}}
delete pointx;
delete pointy;
return 0;}

Why don't add a button "Random Problem" ??

Please, show 9 test.
Who make this problem, public your solution, please.

I used Tarjan Algo, based on DFS and union-find sets, but got Crash AV #3. I made a extreme data myself, like a chain from Node #0. And it really crashed with DEV-C++. I tried to enlarge the size of stack, but it seemed workless. After debugging for so long, I still can't explain why it got stuck at Node #49xxx (The program works on every "smaller data"). Do I have to make a "stack" myself? No, I came up with an idea--randomize. And with that I ACed with no difficulty.
Here is the thing, maybe you picked Node #0 as the root of the tree, but why not change to a random one? I think data #3 is such a data that will make the first algo crash.
Sorry for my poor English, btw.

subj

Странно, но со struct работает и у меня; но не на сервере. У меня libc6.

#include <stdio.h>
#include <math.h>

struct Node // РЕШЕНИЕ: ЗДЕСЬ НУЖНО ПИСАТЬ class. Компилятор тимуса ругается почему-то.
{
    public:
    Node* prev;
    double info;
};

int main()
{
    Node* p = NULL;
    Node* node;
    double d;
    while(scanf("%lf",&d)!=EOF)
    {
        node = new Node;
        node->info = sqrt(d);
        node->prev = p;
        p = node;
    }

    while (p != NULL)
    {
        printf("%.4lf\n", p->info);
        p = p->prev;
    }
    return 0;
}

Edited by author 31.12.2009 03:44

I have got AC for this problem but my solution is quite inefficient

http://acm.timus.ru/status.aspx?space=1&num=1119&author=82952

It takes me 0.156 seconds to compute the answer, but there are many ppl who got solution in 0.015 secs.If possible please email me one of the efficient solution (C++ one).my email address is pjas002@aucklanduni.ac.nz

Thanks

Would anyone happen to know what test #12 is, or otherwise suggest something similar? Because I keep getting Time limit exceeded on it.

Thanks in advance.

http://vkontakte.ru/club1916204
All russians users vkontakte.ru go in this group)

Please give me some test or hint.

#include <stdio.h>
#include <math.h>
int main(){

freopen("b.in","r",stdin);
freopen("b.out","w",stdout);
double x[102],y[102];
double d1,d2;
int i,star=0,k,m,n,j;
double s,r,pi=2*acos(0);

scanf("%d",&k);

for(m=0;m<k;m++){
    s=0;
scanf("%d %Lf",&n,&r);

for(i=0;i<n;i++)
scanf("%Lf %Lf \n",&x[i],&y[i]);
for(j=0;j<n-1;j++){
    d1=abs(x[j]-x[j+1]);
d2=abs(y[j]-y[j+1]);
s=s+sqrt(d1*d1 + d2*d2);

}
  d1=abs(x[0]-x[n-1]);
d2=abs(y[0]-y[n-1]);
s=s+sqrt(d1*d1 + d2*d2);

s=s+(n*pi*r)/2;

if(star==0) star=1;
else printf("\n");
printf("%.2Lf",s);
}
return 0;
}

using System;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            string razd=":;, -";
            string kp=".!?";
            string dig = "0123456789";
            string[] input = Console.In.ReadLine().Split(
            new char[] {  '\n', '\r' }, StringSplitOptions.RemoveEmptyEntries);
            int cnt = 0;
            int ns = 0;
            int nb = 0;
            for (int i = 0; i < input.Length; i++)
            {
                string s = input[i];
                for (int j = 0; j < s.Length; j++)
                {
                    if ((s[j] >= 'A' && s[j] <= 'Z') || (s[j]>='a' && s[j]<='z') || dig.IndexOf(s[j])>=0)
                    {
                        nb++;
                        if (ns == 0) ns++;
                        if (nb == 1 && ns == 1 && (s[j] >= 'a' && s[j] <= 'z')) cnt++;
                        if ((s[j] >= 'A' && s[j] <= 'Z') && nb > 1) cnt++;
                    }
                    if (razd.IndexOf(s[j]) >= 0)
                    {
                        nb=0;
                        if (ns > 0) ns++;
                    }
                    if (kp.IndexOf(s[j])>=0)
                    {
                        ns = 0;
                        nb = 0;
                    }
                }
                nb = 0;
            }
            Console.WriteLine(cnt.ToString());
            Console.ReadKey();
        }
    }
}

What the answer to test:

    m    k    n
12    3    2    18

I got 53 and WA

I really don't like to do it, but i just can't find what is wrong in my code... In my pc it works pretty fine.. but, i got WA 4#...

my bugged code:

==========================================================

#include <iostream>

using namespace std;

void reordena(int *numeros[],int difzero,int num)
{
    int rdn1,rdn2,aux;

    rdn1 = rand() % difzero;
    rdn2 = rand() % difzero;

    aux = numeros[num][rdn1];
    numeros[num][rdn1] = numeros[num][rdn2];
    numeros[num][rdn2] = aux;
}

void permuta(int *numeros[],int num,int tam)
{
    int cont,cont2,aux,difzero=0,resp=0;
    int mult;
    long int contador=0;

    for(cont=0;cont<tam-1;cont++)
    {
        for(cont2=0;cont2<tam-1;cont2++)
        {
            if(numeros[num][cont2]==0)
            {
                aux = numeros[num][cont2];
                numeros[num][cont2] = numeros[num][cont2+1];
                numeros[num][cont2+1] = aux;
            }
        }
    }

    for(cont=0;cont<tam;cont++)
    {
        if(numeros[num][cont]!=0) difzero++;
    }

    mult=1;
    for(cont=difzero-1;cont>=0;cont--)
    {
        aux=(numeros[num][cont]*mult);
        resp+=aux;
        mult*=10;
    }

    while(resp%7!=0)
    {
        reordena(numeros,difzero,num);
        mult=1;
        resp=0;
        for(cont=difzero-1;cont>=0;cont--)
        {
            aux=(numeros[num][cont]*mult);
            resp+=aux;
            mult*=10;
        }
        contador++;
        if(contador>=1000000)
        {
            numeros[num][0]=0;
            resp=0;
        }
    }

}


int main()
{
    int N,cont,**numeros,*tam;
    char aux[200];

    cin >> N;

    if(N<0) exit(0);
    if(N>10000) exit(0);

    tam = new int[N];
    numeros = new int*[N];
    for(cont=0;cont<N;cont++)
    {
        numeros[cont] = new int[20];
    }

    for(cont=0;cont<N;cont++)
    {
        cin >> aux;
        tam[cont] = strlen(aux);
        if(tam[cont]>20)
        {
            exit(0);
        }

        for(int cont2=0;cont2<tam[cont];cont2++)
        {
            numeros[cont][cont2]=aux[cont2]-'0';
        }

        permuta(numeros,cont,tam[cont]);
    }

    system("cls");
    for(cont=0;cont<N;cont++)
    {
        for(int cont2=0;cont2<tam[cont];cont2++)
        {
            if(numeros[cont][0]==0)
            {
                if(cont2==0) cout << "0";
            }
            else if(numeros[cont][cont2]!=0) cout << numeros[cont][cont2];
        }
        if(cont!=N-1) cout << endl;
    }


    delete [] numeros;
    delete [] tam;

    return 0;
}

========================================================

please, help if you can =/

May be anybody knows, what is specific of the second test? All my examples work correctly, but the second test...... }:-/