TAKMIČENJA IZ PROGRAMIRANJA


Sva pitanja, predloge ili primedbe u vezi sa takmičenjima iz programiranja možete slati na e-mail:

tak.prog@gmail.com

U toku perioda za žalbe, sve žalbe možete slati na ovaj isti e-mail.

tabla.cpp    3,154 b      izvorni kod rešenja
tabla.pas    3,432 b      izvorni kod rešenja
tabla.tests.rar    13,139 b      test primeri

zadatak: Oglasna tabla

Tojin Vomić je veoma savestan student. Kako bi što bolje ispratio svoje (i tuđe) napredovanje tokom studija, mnogo vremena provodi pred oglasnom tablom analizirajući tamo prikazane bodove. Nažalost, Tojin je ovog semestra malo popustio s učenjem, pa mu rezultati na oglasnoj tabli baš i ne idu u korist, te je razmišljao kako ne bi bilo loše da se neki od njih sakriju od očiju javnosti. I baš u tom momentu, dr Grupović je, noseći cedulju na kojoj su rezultati s njegovog poslednjeg kolokvijuma, zamolio Tojina da dotičnu okači na oglasnu tablu. (Sve cedulje na oglasnoj tabli, kao i cedulja profesora Grupovića, okruglog su oblika.)

Tojin je brzo razmišljao: okačiće cedulju tako da pokrije što više već objavljenih rezultata - a što, budući da je izlaznost na kolokvijume prof. Grupovića uvek bila veoma visoka, neće biti teško. No, kako je Tojin ipak student matematike a ne informatike, zamolio je vas da mu pomognete.

Ulaz:

(Ulazni podaci se nalaze u datoteci tabla.in) U prvom redu ulazne datoteke nalazi se prirodan broj n (1 ≤ n ≤ 100), koji predstavlja broj rezultata objavljenih na oglasnoj tabli. U svakom od narednih n redova nalaze se po tri realna broja, pri čemu se u i-tom od tih redova nalaze koordinate centra i-te cedulje, kao i njen poluprečnik. Najzad, u poslednjem redu nalazi se još jedan realan broj, koji predstavlja poluprečnik Tojinove/Grupovićeve cedulje. Koordinate su realni brojevi iz intervala [-1000, 1000]. Poluprečnici su realni brojevi iz intervala [1, 1000]. Svi realni brojevi su dati na najviše 2 decimale.

Izlaz:

(Izlazne podatke upisati u datoteku tabla.out) U prvi i jedini red izlazne datoteke ispisati jedan ceo broj: najveći mogući broj objavljenih rezultata koje Tojin može da pokrije zabadanjem cedulje. Cedulja se smatra pokrivenom samo ako je u potpunosti skrivena od očiju javnosti, tj. ukoliko nijedan delić ne izviruje.

Primer 1:

tabla.in      tabla.out
3
0 1 1
1 0 1.41
0 -1 1
1.92
        
2
fajl: tabla.cpp
/*
  Author: Slobodan Mitrovic
  e-mail: boba5555@gmail.com
  date: 03.06.2009.
*/
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define ffor(_a,_f,_t) for(int _a=(_f),__t=(_t);_a<__t;_a++)
#define all(_v) (_v).begin() , (_v).end()
#define sz size()
#define pb push_back
#define SET(__set, val) memset(__set, val, sizeof(__set))
#define FOR(__i, __n) ffor (__i, 0, __n)
#define sqr(a) ((a) * (a))

using namespace std;

const double EPS = 1e-10;

double a[102], b[102], r[102], R;
int n;

struct tDot{
  double x, y;
  bool ex;
  tDot(){
  }
  
  tDot(double _x, double _y, bool _ex){
    x = _x;
    y = _y;
    ex = _ex;
  }
};

tDot ret1, ret2, ret3, ret4;

void findIntersect(int idx1, int idx2){
  ret1.ex = ret2.ex = ret3.ex = ret4.ex = false;
  double va = -a[idx1], vb = -b[idx1];
  
  double c = sqr(a[idx2] + va) + sqr(r[idx1]) + sqr(b[idx2] + vb) - sqr(r[idx2]);
  
  double A = 4.0 * sqr(a[idx2] + va) + 4.0 * sqr(b[idx2] + vb);
  double B = -4.0 * (a[idx2] + va) * c;
  double C = sqr(c) - 4.0 * sqr(b[idx2] + vb) * sqr(r[idx1]);
  double D = sqr(B) - 4.0 * A * C;
  
  if (fabs(A) < EPS || (fabs(D) > EPS && D < 0.0))
    return;
    
    
  double x1 = (-B + sqrt(D)) / (2.0 * A);
  double x2 = (-B - sqrt(D)) / (2.0 * A);
  
  double y1, y2;
  if (sqr(r[idx1]) >= sqr(x1)){
    y1 = sqrt(sqr(r[idx1]) - sqr(x1));
    
    if (sqr(r[idx2]) - sqr(x1 - (a[idx2] + va)) - sqr(y1 - (b[idx2] + vb)) <= EPS){
      ret1.ex = true;
      ret1.x = x1 - va;
      ret1.y = y1 - vb;
    }
    y1 = -y1;

    if (sqr(r[idx2]) - sqr(x1 - (a[idx2] + va)) - sqr(y1 - (b[idx2] + vb)) <= EPS){
      ret3.ex = true;
      ret3.x = x1 - va;
      ret3.y = y1 - vb;
    }
  }

  if (sqr(r[idx1]) >= sqr(x2)){
    y2 = sqrt(sqr(r[idx1]) - sqr(x2));
    
    if (sqr(r[idx2]) - sqr(x2 - (a[idx2] + va)) - sqr(y2 - (b[idx2] + vb)) <= EPS){
      ret2.ex = true;
      ret2.x = x2 - va;
      ret2.y = y2 - vb;
    }
    
    y2 = -y2;

    if (sqr(r[idx2]) - sqr(x2 - (a[idx2] + va)) - sqr(y2 - (b[idx2] + vb)) <= EPS){
      ret4.ex = true;
      ret4.x = x2 - va;
      ret4.y = y2 - vb;
    }

  }
}

double dist(double x1, double y1, double x2, double y2){
  return sqrt(sqr(x1 - x2) + sqr(y1 - y2));
}

int cnt(tDot dot){
  int ret = 0;
  FOR (i, n)
    if (dist(dot.x, dot.y, a[i], b[i]) + r[i] < R + EPS)
      ret++;
  return ret;
}

int ret = 0;

void updateRet(tDot dot){
  if (!dot.ex)
    return;
  
  ret >?= cnt(dot);
}

int main(){
  freopen("tabla.in", "rt", stdin);
  freopen("tabla.out", "wt", stdout);
  scanf("%d", &n);
  FOR (i, n)
   scanf("%lf %lf %lf", &a[i], &b[i], &r[i]);
  
  scanf("%lf", &R);
  FOR (i, n){
    if (r[i] <= R)
      updateRet(tDot(a[i], b[i], true));
      
    if (r[i] >= R)
      continue;
      
    ffor (j, i + 1, n){
      if (r[j] >= R)
        continue;
        
      a[100] = a[i];
      b[100] = b[i];
      r[100] = R - r[i];
      
      a[101] = a[j];
      b[101] = b[j];
      r[101] = R - r[j];

      findIntersect(100, 101);
      updateRet(ret1);
      updateRet(ret2);
      updateRet(ret3);
      updateRet(ret4);
      
    }
  }
  
  printf("%d \n", ret);  
  return 0;
}
fajl: tabla.pas
var n,i,j,maxpokriva,pokr:longint;
    x,y,r:array[1..100] of real;
    rt,maxx,maxy,veliki_ruzni_izraz,a,b,c,x1,y1,x2,y2:real;
    f:text;
    nnnn:string;
function koliko_pokriva(x1,y1:real):longint;
var k, res:longint;
begin
 res:=0;
 for k:=1 to n do
   if sqr(rt-r[k])-sqr(x1-x[k])-sqr(y1-y[k])>=-0.000001 then
     begin
     inc(res);
     end;
    koliko_pokriva:= res;
end;
procedure proveri_pokrivanje;
begin
 pokr:=koliko_pokriva(x1,y1);
 if pokr>maxpokriva then begin
                          maxpokriva:=pokr;
                          maxx:=x1;
                          maxy:=y1;
                         end;
 pokr:=koliko_pokriva(x2,y2);
 if pokr>maxpokriva then begin
                          maxpokriva:=pokr;
                          maxx:=x2;
                          maxy:=y2;
                         end;
end;
begin
 assign(f,'tabla.in');
 reset(f);
 readln(f,n);
 for i:=1 to n do
   readln(f,x[i],y[i],r[i]);
 readln(f,rt);
 close(f);
 i:=1;
 while (i<=n) do
    if r[i]>rt then begin
                     x[i]:=x[n];
                     y[i]:=y[n];
                     r[i]:=r[n];
                     dec(n);
                    end
               else inc(i);
 maxpokriva:=0;
 for i:=1 to n do
   begin
    pokr:=koliko_pokriva(x[i],y[i]);
    if pokr>maxpokriva then begin
                             maxpokriva:=pokr;
                             maxx:=x[i];
                             maxy:=y[i];
                            end;
   end;
 for i:=1 to n-1 do
   for j:=i+1 to n do
     begin
      veliki_ruzni_izraz:=sqr(rt-r[j])-sqr(rt-r[i])+sqr(x[i])+sqr(y[i])-sqr(x[j])-sqr(y[j]);
      if y[i]<>y[j] then begin
                          a:=1+sqr((x[i]-x[j])/(y[i]-y[j]));
                          b:=-2*x[i]-2*(x[i]-x[j])/(y[i]-y[j])*(veliki_ruzni_izraz/(2*(y[i]-y[j]))-y[i]);
                          c:=sqr(x[i])+sqr(y[i])+sqr(veliki_ruzni_izraz/(2*(y[i]-y[j])))-veliki_ruzni_izraz/(y[i]-y[j])*y[i]-sqr(rt-r[i]);
                          if sqr(b)-4*a*c>=0 then begin
                                                   x1:=(-b+sqrt(sqr(b)-4*a*c))/(2*a);
                                                   x2:=(-b-sqrt(sqr(b)-4*a*c))/(2*a);
                                                   y1:=veliki_ruzni_izraz/(2*(y[i]-y[j]))-x1*(x[i]-x[j])/(y[i]-y[j]);
                                                   y2:=veliki_ruzni_izraz/(2*(y[i]-y[j]))-x2*(x[i]-x[j])/(y[i]-y[j]);
                                                   proveri_pokrivanje;
                                                  end
                         end
                    else if x[i]<>x[j] then begin
                                             x1:=veliki_ruzni_izraz/(2*(x[i]-x[j]));
                                             x2:=x1;
                                             if sqr(rt-r[i])-sqr(x1-x[i])>=0 then begin
                                                                                   y1:=sqrt(sqr(rt-r[i])-sqr(x1-x[i]))+y[i];
                                                                                   y2:=-sqrt(sqr(rt-r[i])-sqr(x1-x[i]))+y[i];
                                                                                   proveri_pokrivanje;
                                                                                  end
                                            end
     end;
 assign(f,'tabla.out');
 rewrite(f);
 writeln(f,maxpokriva:0);
 close(f);
end.