Solution of Evil Geometry

Intrucat precizia ceruta este mica (0.01), vom aproxima aria ceruta. Pentru aceasta putem lua toate punctele de forma (a*eps, b*eps), eps fiind o constanta fixata) din patratul cu colturi (-75, -75) si (75, 75) si apoi numara cate din ele sunt in interiorul a macar una dintre elipse. Notand acest numar cu b, aria devine b * eps2. Aceasta solutie insa iese din timp, avand o complexitate de O(1/eps2).

O optimizare care duce la AC este urmatoarea:
Parcurgem liniile din eps in eps, si pentru fiecare linie parcurgem coloanele din eps*step in eps*step. Retinem la fiecare moment daca ne aflam in interiorul unei elipse sau nu. Daca la un pas de lungime step iesim sau intram din reuniunea elipselor, parcurgem fiecare din aceste step puncte in parte. Solutia oficiala, cu eps = 3e-2 si step = 100 

    1 #include <iostream>
    2 #include <iomanip>
    3 #include <cstdlib>
    4 #define FACT 300
    5 #define STEP 100
    6 using namespace std;
    7 
    8 static struct {
    9     long long x, y, a, b, aa, bb, limit;
   10 
   11     void read() {
   12         cin>>x>>y>>a>>b;
   13         x*=FACT, y*=FACT;
   14         limit = a * a * b * b * FACT * FACT;
   15     }
   16 
   17     bool inside(long long px, long long py) {
   18         return (px - x) * (px - x) * b * b + (py - y) * (py - y) * a * a <= limit;
   19     }
   20 }e1, e2, e3;
   21 
   22 bool inside(int i, int j){
   23     return e1.inside(i, j) || e2.inside(i, j) || e3.inside(i, j);
   24 }
   25 
   26 int main() {
   27     e1.read(); e2.read(); e3.read();
   28     long long bune=0;
   29     for(int i = -75 * FACT; i < 75 * FACT; i++){
   30         int j = -75 * FACT;
   31         bool last = 0;
   32         for(; j < 75 * FACT; j+=STEP){
   33             bool cur = inside(i, j);
   34             if(cur != last)
   35                 for(int k = 0; k < STEP; k++)
   36                     bune += inside(i, j-k);
   37             else if(cur)
   38                 bune += STEP;
   39             last = cur;
   40         }
   41     }
   42     cout << fixed << setprecision(6) << 1.0 * bune / FACT / FACT;
   43 }

Solutie cu 'patratele' (Catalin-Stefan Tiseanu)

Vom incerca sa aproximam aria ceruta (in cazul acesta, a reuniunii de elipse, pe care o vom numi U) cu patratele.

Ideea de baza este ca atat timp cat o zona a patratelului curent nu este in totalitate in U, il impartim in 4 sub patratele egale si apelam recursiv.

Daca zona patratelului este total in afara lui U, ne oprim pt patratelul curent si returnam 0.
Daca zona patratelului este total in U, ne oprim si returnam aria lui. Apelul recursiv se opreste cand aria patratelului curenta este suficient de mica.

Mai exact, pentru a testa relatia patratelului relativ la U este suficient sa ne uitam la cele 4 colturi ale lui:

  1. toate in U (in aceeasi elipsa dupa cum vedem mai jos): returnam aria patratelului (este continut in U)
  2. toata in afara lui U: returnam 0
  3. cel putin unul in afara lui U si cel putin unul inauntrul lui U: apelam recursiv

O optimizare importanta pentru precizie: trebuie sa verificam pentru cele 4 colturi ca se afla in ACEEASI elipsa, nu este suficient sa se afle in elipse diferite pentru ca pot apare cazuri cand o zona din patratel nu este in U, desi toate cele 4 colturi ale lui sunt in U. 

    1 // x, y - coordonatele stanga jos ale patratelului
    2 // l - latura curenta
    3 inline double rec (double x, double y, double l) {
    4 	double area = l * l;
    5 	if (area <= EPSILON * EPSILON)
    6 		return area / 2;
    7 	++counter; // cate operatii facem
    8 	int msk[3] = {1, 1, 1};
    9 	int sum = in_ellipses(mp(x, y), msk) +
   10 		in_ellipses(mp(x + l, y), msk) +
   11 		in_ellipses(mp(x, y + l), msk) +
   12 		in_ellipses(mp(x + l, y + l), msk);
   13 	// (msk[i] == 1) = toate cele 4 puncte se afla in elipsa i
   14 	// all in same elipse
   15 	if(msk[0] + msk[1] + msk[2])
   16 		return area; // cel putin un msk[i] != 0 => cel putin o elipsa contine toate colturile
   17 	else if (sum == 0) // toate in afara lui U
   18 		return 0.0;
   19 	return rec(x, y, l / 2) +
   20 		rec(x + l / 2, y, l / 2) +
   21 		rec(x, y + l / 2, l / 2) +
   22 		rec(x + l / 2, y + l / 2, l / 2);
   23 }
Apelul initial se face pe toate patratelele de arie 1 si coordonate intregi din zona de interes (MIN_COORD ... MAX_COORD).

Solutie Mihai Popa

La fel ca in cazul celorlalte solutii, vom incerca sa aproximam aria ceruta. Ne impartim planul in dreptunghiuri de latime eps = 1e-4 (pe axa OX) si inaltime infinit (pe axa OY). Asadar, planul va fi impartit in dreptunghiuri cu coltul din stanga jos (x,-infinit) si coltul din dreapta sus (x+eps,+infinit). Parcurgem pe rand x-ii care reprezinta o latura a unui dreptunghi si calculam intersectiile lor cu elipsele. Pentru un x fixat, nu este foarte dificil sa calculam suma lungimilor segmentelor paralele cu OY la x-ul curent care se afla in interiorul cel putin unei elipse. Sa notam aceasta suma cu s. Acum putem aduna la solutie s*eps, corespunzand ariei aproximate apartinand dreptunghiului (x,-infinit), (x+eps,infinit) care se afla in interiorul cel putin unei elipse.
Questions?

Sponsors Gold