Farmer Joca je na svojoj beskonačnoj njivi, da bi se lakše snalazio, postavio pravougli koordinatni sistem i povukao prave paralelne koordinatnim osama na međusobnom odstojanju od 1 metar, pri čemu i koordinatne ose pripadaju ovom skupu pravih. Na taj način dobio je polja dimenzije 1x1 metar. I tako je on srećno ubirao plodove, sve dok jednog dana na njegovu njivu nije pao meteor. Na žalost, nije mogao da ga pomeri, pa je odlučio da ne obrađuje polja čiju je unutrašnjost meteorit makar i malo prekrio iz razloga što je on usavršio mašine koja obrađuju cela polja odjednom.

Farmer Joca je detaljnom analizom ustanovio da meteor ima osnovu oblika kruga. Zatim je ustanovio njegov poluprečnik i koordinate centra (mereći u njegovom koordinatnom sistemu). Dajući vam ove podatke, on vas je zamolio da mu pomognete u određivanju površine dela zemljišta koji više neće koristi.

Ulaz:

U prvom i jedinom redu ulaznog tekstualnog fajla meteor.in nalaze se tri realna broja X, Y i R sa preciznošću od 2 decimale (-10^6 ≤ X, Y ≤ 10^6, 0 ≤ R ≤ 10^6), razdvojena blanko znakom, koji predstavljaju X i Y koordinate centra i poluprečnik osnove meteora u metrima.

Izlaz:

U prvi i jedini red izlaznog tekstualnog fajla meteor.out upisati ceo broj P koji predstavlja površinu dela zemljišta koju farmer Joca više neće koristiti izraženu u kvadratnim metrima.

Primer:

-0.50 3.00 2.50

26

Objašnjenje:

Slika odgovara primeru. Koordinatne ose su obeležene sa X i Y, a horizontalne i vertikalne linije paralelne njima su na međusobnom odstojanju od 1 metar. Krug odgovara osnovi meteora, a zatamnjena polja odgovaraju onim koja farmer Joca više neće obrađivati.

Zadatak možemo preformulisati na sledeći način. Za zadati krug u ravni je potrebno naći broj celobrojnih kvadratića koji sa krugom imaju presek površine veće od nula. Celobrojni kvadratići su oni omeđeni pravama oblika x=X, x=X+1, y=Y i y=Y+1, gde su X i Y celobrojne konstante. Ovde i nadalje malim slovima označavaćemo koja je koordinata u pitanju, a velikim slovima brojevne vrednosti.

Rešenje zadatka je intuitivno. Potrebno je skanirati krug npr. po z koordinati, posmatrati preseke kruga sa parovima uzastopnih linija skaniranja y=Y i y=Y+1 (gde je Y ceo broj), i na osnovu njih odrediti broj celobrojnih kvadratića između ove dve linije i to dodati ukupnom rezultatu.

Da bismo ovo formalizovali definišimo sledeće pojmove: x-traka(X) je deo ravni omeđen pravama x=X i x=X+1, y-traka(Y) je deo ravni omeđen pravama y=Y i y=Y+1, x-traka(X1) je levo od x-trake(X2) ako je X1 < X2, y-traka(Y1) je niže od y-trake(Y2) ako je Y1 < Y2, analogno definišemo pojmove desno i niže. Nakon ovoga možemo formulisati algoritam za rešavanje zadatka:

  Y_donja_traka := naći najnižu y-traku koja ima presek sa krugom;
  Y_gornja_traka := naći najvišu y-traku koja ima presek sa krugom;
  Broj_kvadratića := 0;
  for Y := Y_donja_traka to Y_gornja_traka do
  begin
    X_leva_traka(Y) := naći najlevlju x-traku koja u y-traci(Y) ima presek sa krugom;
    X_desna_traka(Y) := naći najdesniju x-traku koja u y-traci(Y) ima presek sa krugom;
    Broj_kvadratića_u_traci := X_desna_traka(Y) - X_leva_traka(Y) + 1;
    Broj_kvadratića := Broj_kvadratića + Broj_kvadratića_u_traci;
  end;

U cilju skaniranja kruga po trakama potrebno je naći granične trake, tj. najdonju i najgornju traku koje imaju presek sa njim. Za to nam je potrebno odrediti tačke kruga sa najmanjom i najvećom y koordinatom. Neka su Xc i Yc koordinate centra, a R poluprečnik kruga. "Najniža" tačka kruga ima y koordinatu Y_donja_granica = Yc - R. "Najviša" tačka kruga ima y koordinatu Y_gornja_granica = Yc + R. Slično, "najlevlja" tačka kruga ima x koordinatu X_leva_granica = Xc - R. "Najdesnija" tačka kruga ima x koordinatu X_desna_granica = Xc + R.

Razmotrimo kako na osnovu realnih vrednosti Y_donja_granica i Y_gornja_granica dobiti celobrojne vrednosti Y_donja_traka i Y_gornja_traka. Može se pokazati da je Y_donja_traka najveći ceo broj ne veći od Y_donja_granica, a Y_gornja_traka najveći ceo broj manji od Y_gornja_granica. Razlika je u načinu razrešenja slučaja kada je granica celobrojna. Slično možemo odrediti X_leva_traka kao najveći ceo broj ne veći od X_leva_granica, a X_desna_traka kao najveći ceo broj manji od X_desna_granica.

Ostaje nam da za datu y-traku(Y) nađemo najlevlju i najdesniju x-traku koja ima presek sa krugom. Za to je potrebno naći najlevlju i najdesniju tačku kruga u toj y-traci. S obzirom na geometriju kruga, sve y-trake možemo razvrstati u tri grupe: prvu čini traka koja sadrži centar kruga - centralna traka (ako centar kruga ima celobrojnu y koordinatu centralna traka može biti bilo koja od dve granične, a mogu se i obe posmatrati kao centralne). Drugu grupu čine trake iznad centralne; treću grupu čine trake ispod centralne. Za svaku y-traku(Y) koja je iznad centralne najlevlja i najdesnija tačka kruga dobijaju se u preseku kružnice i prave y=Y, na osnovu kojih (odnosno njihovih x koordinata) se nalaze X_leva_traka(Y) i X_desna_traka(Y). Za svaku y-traku(Y) koja je ispod centralne najlevlja i najdesnija tačka kruga dobijaju se u preseku kružnice i prave y=Y+1. Za centralnu traku najlevlja i najdesnija tačka kruga imaju x koordinate X_leva_granica i X_desna_granica, a najlevlja i najdesnija traka su X_leva_traka i X_desna_traka. Centralnu traku dobijamo na sledeći način: Centralna_traka je najveći ceo broj manji (ne veći) od Yc. Razlika je u tome što kad je Yc ceo broj u slučaju da se upotrebi relacija "manji" bira se donja, a u slučaju relacije "ne veći" bira se gornja od dve ravnopravne trake.

Konačno, rešenje možemo iskazati sledećim algoritmom:

  Algoritam_za_rešavanje_zadatka_meteor
  Ulaz: Xc, Yc, R
  Izlaz: Broj_kvadratića
  begin
    Y_donja_granica := Yc - R;
    Y_gornja_granica: = Yc + R;
    Y_donja_traka := najveći_ceo_broj_ne_veći_od( Y_donja_granica);
    Y_gornja_traka := najveći_ceo_broj_manji_od(Y_gornja_granica);
    X_leva_granica := Xc - R;
    X_desna_granica: = Xc + R;
    X_leva_traka := najveći_ceo_broj_ne_veći_od(X_leva_granica);
    X_desna_traka := najveći_ceo_broj_manji_od(X_desnA_granica);
    Centralna_traka := najveći_ceo_broj_manji_od(Yc);
    Broj_kvadratića := X_desna_traka - X_leva_traka + 1; /*inicijalizacija centralnom trakom*/
    for Y := Y_donja_traka to Centralna_traka - 1 do
    begin
      X_leva_granica(Y) i X_desna_granica(Y) su x koordinate preseka kružnice i prave y=Y+1;
      /* X_leva_granica(Y) < X_desna_granica(Y) */
      X_leva_traka(Y) := najveći_ceo_broj_ne_veći_od(X_leva_granica(Y));
      X_desna_traka(Y) := najveći_ceo_broj_manji_od(X_desna_granica(Y));
      Broj_kvadratića_u_traci := X_desna_traka(Y) - X_leva_traka(Y) + 1;
      Broj_kvadratića := Broj_kvadratića + Broj_kvadratića_u_traci;
    end;
    for Y := Centralna_traka + 1 to Y_gornja_traka do
    begin
      X_leva_granica(Y) i X_desna_granica(Y) su x koordinate preseka kružnice i prave y=Y;
      /* X_leva_granica(Y) < X_desna_granica(Y) */
      X_leva_traka(Y) := najveći_ceo_broj_ne_veći_od(X_leva_granica(Y));
      X_desna_traka(Y) := najveći_ceo_broj_manji_od(X_desna_granica(Y));
      Broj_kvadratića_u_traci := X_desna_traka(Y) - X_leva_traka(Y) + 1;
      Broj_kvadratića := Broj_kvadratića + Broj_kvadratića_u_traci;
    end;
  end.

Složenost: Vremenska složenost rešenja je O(ceo_deo(R)), a memorijska složenost O(const).

Implementacione pojedinosti: Kod realizacije funkcija za određivanje najvećeg celog broja koji je manji od datog realnog broja i najvećeg celog broja koji nije veći od datog realnog broja potrebno je posebno razmatrati pozitivne, a posebno negativne brojeve zbog specifičnosti funkcije odsecanja, a nulu priključiti jednom od ova dva slučaja.

Primetimo da rešenje ne zavisi od celog dela koordinata centra kruga, već samo od razlomljenog dela, jer se translacijom koordinata za ceo broj po nekoj od koordinata ono ne menja. To znači da ove koordinate možemo svesti tako da im je ceo deo nula. Ovo doprinosi manjim vrednostima realnih brojeva sa kojima se radi, što daje i manju grešku izvršenja operacija nad njima. To naravno nije presudno u rešavanju zadatka, ali je interesantno spomenuti.

Broj_kvadratića može prevazilaziti 32-bitni format. Zato je potrebno koristiti 64-bitne brojeve. Umesto toga moguća je i realizacija sa dva 32-bitna broja, od kojih jedan čuva količnik a drugi ostatak pri deljenju rezultata sa nekom velikom 32-bitnom konstantom. Maksimalni rezultat ne prevazilazi (2*ceo_deo(R+1))2 = (2*106)2 = 4*1012, pa se, na primer, može uzeti konstanta 108.

Ulazni podaci su dati sa preciznošću od 8 dekadnih cifara. S obzirom da 8-bajtni brojevi sa pokretnom zapetom imaju preciznost od 15 dekadnih cifara, iz predostrožnosti od grešaka zaokruživanja nakon operacija množenja i kvadriranja, preporučuje se upotreba 10-bajtnog proširenog formata brojeva sa pokretnom zapetom koji ima preciznost od 19 dekadnih cifara.

/*
ZADATAK: meteor
JEZIK: c
*/

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

#define floattype double
#define breaks 100000000
#define step 8
#define eps 1E-10

FILE *inFile, *outFile;
floattype Cx, Cy, R;
long rez, rezV;

void ucitavanje() {
  fscanf(inFile, "%lf %lf %lf", &Cx, &Cy, &R);
  Cx -= (long)Cx;
  Cy -= (long)Cy;
}

int jednako(floattype a, long b) {
  if (fabs(a - (floattype)b) < eps) return 1;
  else return 0;
}

// nalazi najveci ceo broj manji od datog broja
long findmax(floattype value) {
  long ret;
  if (value > 0)
  {
    ret = (long) value;
    if (jednako(value, ret)) ret--;
  }
  else ret = (long) (value - 1);
  return ret;
}

// nalazi najveci ceo broj ne veci od datog broja
long findmin(floattype value) {
  long ret;
  if (value >= 0) ret = (long) value;
  else
  {
    ret = (long) (value - 1);
    if (jednako(value, ret + 1)) ret++;
  }
  return ret;
}

void obrada() {
// deklaracije promenljivih
  floattype maxX, maxY, minX, minY, d, Xmin, Xmax;
  long maxIX, maxIY, minIX, minIY, CIy, yI, XminI, XmaxI;

// odredjivanje granica
  maxY = Cy + R;
  minY = Cy - R;
  maxX = Cx + R;
  minX = Cx - R;
  maxIY = findmax(maxY);
  minIY = findmin(minY);
  maxIX = findmax(maxX);
  minIX = findmin(minX);
  CIy = findmax(Cy);

// izracunavanje - glavni deo
  rez = maxIX - minIX + 1;
  rezV = 0;
  for (yI = CIy + 1; yI <= maxIY; yI++)
  {
    d = pow(pow(R, 2) - pow(yI - Cy, 2), 0.5);
    Xmin = Cx - d;
    Xmax = Cx + d;
    XmaxI = findmax(Xmax);
    XminI = findmin(Xmin);
    rez += XmaxI - XminI + 1;
    if (rez >= breaks)
    {
      rezV += rez / breaks;
      rez = rez % breaks;
    }
  }
  for (yI = CIy - 1; yI >= minIY; yI--)
  {
    d = pow(pow(R, 2) - pow(yI + 1 - Cy, 2), 0.5);
    Xmin = Cx - d;
    Xmax = Cx + d;
    XmaxI = findmax(Xmax);
    XminI = findmin(Xmin);
    rez += XmaxI - XminI + 1;
    if (rez >= breaks)
    {
      rezV += rez / breaks;
      rez = rez % breaks;
    }
  }
}

void stampanje() {
  long i, b = breaks;
  if (rezV > 0)
  {
    fprintf(outFile, "%ld", rezV);
    for (i = 0; i < step; i++)
    {
      b /= 10;
      fprintf(outFile, "%ld", rez / b);
      rez = rez % b;
    }
    fprintf(outFile, "\n");
  }
  else fprintf(outFile, "%ld\n", rez);
}

long main() {
  inFile = stdin;//fopen("meteor.in", "r");
  outFile = stdout;//fopen("meteor.out", "w");

  ucitavanje();
  obrada();
  stampanje();

//    fclose(inFile);
//    fclose(outFile);

  return 0;
}