|
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.
|
logo by Igor Antolović
|
|
|
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.
|
|
|