1302 Cercuri4

[•klamathix]

Aici puteti discuta despre problema Cercuri4.

[•alexandra_sandu]

"ÃŽn continuare, el vrea să  alegă un număr oarecare de cercuri - fie acestea C1, C2 ... Ck - astfel încât Ci+1 este inclus in Ci, pentru 1 ≤ i ≤ k-1."

Cum se defineste in Dicționarul explicativ al limbii române verbul a alegă.

[•SpiderMan]

S-a incurcat si omu, de ce esti rea .

[•ctlin04]

Ajutati-ma si pe mine cu problema asta, abia am inceput sa invat cpp si nu pot sa inteleg de ce iau incorect pe trei teste, este vreo greseala in algoritm sau sunt careva particularitati in cpp???  
Cod:
...

[•vendetta]

la apelarea sort-ului din STL ai gresit parametri... Mai concret trebuie sa pui ca parametri a+1 in loc de a si respectiv a+n+1 in loc de a+n pentru ca indexarea o faci de la 1 la n nu de la 0 la n-1... Prin acei paremetrii trimiti niste pointeri, adresa de inceput respectiv de final(sper ca m-am pronuntat corect)

[•ctlin04]

Mda, asta era ms mult 

[•visanr]

Am trimis mai multe surse care primesc 0 pct cu incorect pe toate testele. E gresit cum verific daca un cerc e inclus in altul?

Cod:

double dist(int i, int j)
{
       return sqrt(1.0 * (v[i].X - v[j].X) * (v[i].X - v[j].X) +  1.0 * (v[i].Y - v[j].Y) * (v[i].Y - v[j].Y));
}

bool compare(int i, int j)
{
      double distanta = dist(i, j);
      double minn, maxx;
      if(v[i].R < v[j].R)
      {
               minn = 1.0 * v[i].R;
               maxx = 1.0 * v[j].R;
      }else
      {
            minn = 1.0 * v[j].R;
            maxx = 1.0 * v[i].R;
      }
      if(distanta + minn < maxx) return true; 
      if(abs(distanta + minn - maxx) < eps) return true;
      return false;
}

Fac la fel ca in solutia oficiala..

[•ctlin04]

La problema asta imi amitesc am considerat ca un cerc da raza mai mica se include intr-un cerc de raza mai mare, daca disdanta dintre centrele lor+raza cercului mai mic<=raza cercului mai mare, cam asta e tot un singur if 

[•visanr]

Am trimis si asa si tot 0 iau:

Cod:

bool compare(int i, int j)
{
      if(dist(i, j) + 1.0 * min(v[i].R, v[j].R) <= 1.0 * max(v[i].R, v[j].R)) return true; 
      return false;
}

Am facut razele double deoarece functia dist returneaza double.
In rest mai am o sortare, 2 for-uri ca sa fac vectorul best si cam atat.

Rezolvarea completa: http://pastebin.com/6rMtT5TB

[•tzipleatud]

Am trimis si asa si tot 0 iau:

Cod:

bool compare(int i, int j)
{
      if(dist(i, j) + 1.0 * min(v[i].R, v[j].R) <= 1.0 * max(v[i].R, v[j].R)) return true; 
      return false;
}

Am facut razele double deoarece functia dist returneaza double.
In rest mai am o sortare, 2 for-uri ca sa fac vectorul best si cam atat.

Rezolvarea completa: http://pastebin.com/6rMtT5TB

Salut! M-am uitat peste sursa ta si am observat niste greseli:

1) foloseste long long pentru dimensiunile cercului. La mine asta a facut diferenta intre 0 si 100 de puncte.
2) in dinamica aceea, tu trebuie sa determini maximul din vectorul best, nu maximul dintre gradul de frumusete al cercului. Tu ceea ce faci va determina defapt gradul maxim al cel mult 2 cercuri inscrise unul intr-altul. Adica in loc de maxim=max(maxim,v[j].F) pune maxim=max(maxim,best[j])
3) cand afisezi raspunsul nu e neaparat ca best[N-1] sa fie maximul din vectorul best, asa ca determina maximul din vectorul best si acel maxim afiseaza-l.

Sper ca aceste observatii sa te ajute! Bafta!

Da-mi un mesaj daca vrei sa iti trimit sursa ta modificata si care ia 50 puncte, cu restul TLE.

[•visanr]

LE: 100, multumesc pt ajutor!

Greseli pe care nu le-am facut niciodata  Relatia de recurenta e gresita si in articolul cu solutii. 

[•darkseeker]

Multumesc de observatie. Am modificat-o .

[•geniucos]

Ma puteti ajuta si pe mine?Fac exact ca in articolul cu solutii si am 6 TLE-uri si 4 WA.Nu vad nicio greseala.
Asta este sursa

Cod:

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
long long maxi1,n,i,j,maxi,b[3005];
struct str
{
    int x,y,r,f;
};
str a[3004];
bool cmp(str a,str b)
{
    return a.r<b.r;
}
double dist(int i,int j)
{
    return (double)pow(1LL*(a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y),0.5);
}
bool incl(int j,int i)
{
    if((double)dist(i,j)<=a[i].r-a[j].r) return 1;
    return 0;
}
int main()
{
freopen("cercuri4.in","r",stdin);
freopen("cercuri4.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
{
    scanf("%d",&a[i].x);
    scanf("%d",&a[i].y);
    scanf("%d",&a[i].r);
    scanf("%d",&a[i].f);
}
sort(a+1,a+n+1,cmp);
maxi1=0;
for(i=1;i<=n;i++)
{
    maxi=0;
    for(j=1;j<i;j++)
        if(incl(j,i)&&b[j]>maxi) maxi=b[j];
    b[i]=1LL*maxi+a[i].f;
    if(b[i]>maxi1) maxi1=b[i];
}
printf("%d\n",maxi1);
return 0;
}

Daca vedeti ceva gresit imi puteti spune,va rog.Multumesc anticipat.

[•repp4radu]

In primul rand, poti avea erori de precizie cand compari un double cu un int in functia incl(cred ca de aici iti vine problema <eu nu am mai vazut altceva dubios>).
Ca sa eviti chestia asta, poti sa nu mai faci radical din distanta dintre centrele cercurilor, iar in schimb sa compari cu patratul diferentei razelor.
E acelasi lucru dpdv matematic, doar ca radicalul se executa mult mai incet decat o inmultire.
In al doilea rand, cand vrei sa postezi [ i ], lasa spatiu intre i si paranteze pentru ca altfel totul va aparea in italic, iar indicele va disparea de la locul lui.

Ca o mentiune, eu am sortat descrescator dupa raze, dar nu vad niciun motiv pentru care asta ar conta.

Spor!

[•superman_01]

Buna seara,
Ma chinui la problema asta si nu imi dau seama ce am gresti,aparent totul pare bine.Poate cineva sa imi zica ce am gresit ?
Multumesc anticipat!

[•new_programmer]

Buna seara,
Ma chinui la problema asta si nu imi dau seama ce am gresti,aparent totul pare bine.Poate cineva sa imi zica ce am gresit ?
Multumesc anticipat!

Din pacate, membrii infoarenei nu ajuta in felul acesta.
Iti sugerez sa te uiti peste comentariile anterioare si sa vezi daca este vreo corelatie intre infundatura ta si ele.
Alte optiuni ar fi sa explici cum abordezi problema sau sa te uiti peste solutia oficiala si sa folosesti testele de la evaluator.
Dar cea mai buna, IMO, este sa-ti dai tu teste cat mai istete. Nu trebuie sa fie numere mari.

[•superman_01]

Alte optiuni ar fi sa explici cum abordezi problema sau sa te uiti peste solutia oficiala si sa folosesti testele de la evaluator.

Ca si idee am implementat solutia oficiala ... am avut grija sa nu apara erori de precizie. Nu stiu de la ce poate fi greseala. Si cum pot folosi teste din evaluator ? ( sper ca am inteles eu bine la ce te referi)

[•new_programmer]

Ca si idee am implementat solutia oficiala ... am avut grija sa nu apara erori de precizie. Nu stiu de la ce poate fi greseala. Si cum pot folosi teste din evaluator ? ( sper ca am inteles eu bine la ce te referi)

Scuze, am confundat problema aceasta cu alta problema care tot "cercuri" se numea. Aceea problema era data la OJI si era posibil sa descarci testele oficiale si sa verifici ce rezultate primesti. Deci pentru aceasta problema nu sunt teste de downloadat (cel putin la prima vedere).

Daca spui ca e acceasi implementare ca si solutia oficiala, verifica bine dacaca codul tau face ceea ce ti-ai propus tu sa faca. Tot timpul, in problemele de algoritmica, o mare parte ocupa testarea. O alta alternativa e sa postezi pe stack overflow (pentru asta trebuie sa stii engleza) si acolo deobicei se gasesc persoane sa raspunde in minute si te ajuta pana in capat.

[•superman_01]

mi-a iesit pana la urma . nu pusesem long long unde trebuia si de aia luam 0