Input:
Code: Select all
12 28 15
1 10
5 19
19 3
5 6
6 2
8 2
12 16
3 8
17 12
5 3
14 13
3 2
Code: Select all
-1
Moderator: Board moderators
Code: Select all
12 28 15
1 10
5 19
19 3
5 6
6 2
8 2
12 16
3 8
17 12
5 3
14 13
3 2
Code: Select all
-1
Thanks a lot.Jan wrote:I havent checked why you are getting RTE but I can say that your code isnt correct. Check the case
Input:Output:Code: Select all
12 28 15 1 10 5 19 19 3 5 6 6 2 8 2 12 16 3 8 17 12 5 3 14 13 3 2
Hope it helps.Code: Select all
-1
Code: Select all
#include <iostream>
#include <cmath>
#include <cstdlib>
using namespace std;
struct node
{
double begin, end;
} section[10001];
inline int cmp(const void* a, const void* b)
{
return ((node*)a)->begin > ((node*)b)->begin ? 1 : -1;
}
int main()
{
int n, l, w, r, pos;
while (cin >> n)
{
cin >> l >> w;
double w2 = double(w*w)/4;
for (int i = 1; i <= n; i++)
{
cin >> pos >> r;
double tmp = sqrt(r*r-w2>0 ? r*r-w2 : 0);
section[i].begin = pos - tmp;
section[i].end = pos + tmp;
}
qsort(§ion[1], n, sizeof(node), cmp);
double st = 0;
int count = 0, p = 0;
if (section[1].begin > 0 || n <= 0 || w <= 0 || l <= 0)
{
cout << "-1\n";
st = l;
count = -1;
}
while (st < l)
{
double tmpmax = 0;
int maxi = p;
int pre = maxi; //In order to check wheather it's able to find the next section
while (section[++p].begin - st < 1e-8 && p <= n)
if (section[p].end - st > tmpmax)
{
tmpmax = section[p].end - st;
maxi = p;
}
if (maxi == pre)
{
cout << "-1\n";
st = l;
count = -1;
}
else
{
st = section[maxi].end;
count++;
}
}
if (count > 0)
cout << count << endl;
}
return 0;
}
Code: Select all
2 26 6
4 10
16 14
10 6 37
20 4
19 20
19 2
8 4
7 19
7 14
3 17
1 19
18 1
15 19
Code: Select all
2
2
Really thanks for your datas. It just helped me find a mistake. But I still get WA. I've been very confused. Could you please give me some advice? Thanks a lot.Jan wrote:Try the cases.
Input:Output:Code: Select all
2 26 6 4 10 16 14 10 6 37 20 4 19 20 19 2 8 4 7 19 7 14 3 17 1 19 18 1 15 19
Hope these help.Code: Select all
2 2
I checked this test case too and it produced the correct output with my binary. now I guess that there might be some coflicts with the compilers.Jan said:
I havent checked why you are getting RTE but I can say that your code isnt correct. Check the case
Input:
Code:
12 28 15
1 10
5 19
19 3
5 6
6 2
8 2
12 16
3 8
17 12
5 3
14 13
3 2
Output:
Code:
-1
Code: Select all
int double
a == b fabs(a-b) < eps
a != b fabs(a-b) > eps
a > b a > b + eps
a < b a + eps < b
Code: Select all
const double EPS = 1e-11;
typedef pair<double, double> pii;
bool solve() {
int n, l, w;
if (scanf("%d %d %d ",&n,&l,&w) != 3)
return false;
vector<pii> sprinklers;
for (int i = 0; i < n; i++) {
int p, r;
scanf("%d %d ",&p,&r);
pii pd;
if (2 * r > w) {
double d = sqrt(r * r - (w * w) / 4.0);
pd.first = p - d;
pd.second = p + d;
sprinklers.push_back(pd);
}
}
sort(sprinklers.begin(), sprinklers.end());
int m = SZ(sprinklers);
double start = 0;
int j = 0, total = 0, pj = 0;
while (start < (double)l - EPS) {
double go = start;
while (j < m && sprinklers[j].first - EPS < start) {
go = max(go, sprinklers[j].second);
j++;
}
if (pj == j) {
printf("-1\n");
return true;
}
pj = j;
start = go;
total++;
}
printf("%d\n", total);
return true;
}
Code: Select all
double length_2 = sqrt((double)(rad*rad)-w2_2);
Code: Select all
double length_2 = sqrt((double)rad*rad-w2_2);
Code: Select all
var p,pi,t,len,n,w,i,tot:longint;
l,r:array[0..10000]of double;
now,max:double;
flag:boolean;
procedure qsort(x,y:longint);
var i,j:longint;
k,temp:double;
begin
i:=x;j:=y;k:=l[(i+j) div 2];
repeat
while l[i]<k do inc(i);
while l[j]>k do dec(j);
if not (i>j) then begin
temp:=l[i];l[i]:=l[j];l[j]:=temp;
temp:=r[i];r[i]:=r[j];r[j]:=temp;
inc(i);dec(j);
end;
until i>j;
if x<j then qsort(x,j);
if i<y then qsort(i,y);
end;
begin
while not eof do begin
readln(n,len,w);
t:=0;
for i:=1 to n do begin
readln(p,pi);
if pi>w/2 then begin
inc(t);
l[t]:=p-sqrt(sqr(pi)-sqr(w/2));
if l[t]<0 then l[t]:=0;
r[t]:=p+sqrt(sqr(pi)-sqr(w/2));
if r[t]>len then r[t]:=len;
//writeln(l[t],' ',r[t]);
end;
end;
qsort(1,t);
now:=0;
i:=1;
tot:=0;
flag:=true;
while now<len do begin
max:=0;
while (l[i]<=now) and (i<=t) do begin
if r[i]>max then max:=r[i];
inc(i);
end;
if max=0 then begin
writeln(-1);
flag:=false;
break;
end;
now:=max;
inc(tot);
end;
if flag then writeln(tot);
end;
end.
Code: Select all
#include <iostream>
#include <cmath>
using namespace std;
int n;
int sX [ 10000 ], sR [ 10000 ];
int l, w;
struct Line
{
double l, r;
} ln [ 10000 ];
void process();
void construct();
int main()
{
while ( cin >> n >> l >> w )
{
for ( int i = 0; i < n; i++ )
{
cin >> sX[ i ] >> sR[ i ];
}
process();
}
return 0;
}
void process()
{
construct();
double cV;
cV = 0;
Line tLn [ 10000 ];
int tNo;
int cnt = 0;
while ( cV < l && n > 0 )
{
int next = -1;
for ( int i = 0; i < n; i++ )
{
if ( next == -1 )
{
next = i;
}
else if ( (ln[ i ].l < ln[ next ].l) ||
(ln[ i ].l == ln[ next ].l && ln[ i ].r > ln[ next ].r) )
{
next = i;
}
}
if ( ln[ next ].l > cV )
{
cout << -1 << endl;
return;
}
cV = ln[ next ].r;
cnt++;
tNo = 0; // refresh
for ( int j = 0; j < n; j++ )
{
if ( ln[ j ].l < cV )
{
if ( ln[ j ].r <= cV )
{
// do nothing
}
else
{
ln[ j ].l = cV;
tLn[ tNo++ ] = ln[ j ];
}
}
else
{
tLn[ tNo++ ] = ln[ j ];
}
}
for ( int j = 0; j < tNo; j++ )
{
ln[ j ] = tLn[ j ];
}
n = tNo;
}
if ( cV < l )
{
cout << -1 << endl;
}
else
{
cout << cnt << endl;
}
}
void construct()
{
double tL, tR;
int tCnt = 0;
for ( int i = 0; i < n; i++ )
{
if ( sR[ i ] > w / 2.0 )
{
tL = max( sX[ i ] - sqrt( 4 * sR[ i ] * sR[ i ] - w * w + 0.0 ) / 2.0 , 0.0 );
tR = min( sX[ i ] + sqrt( 4 * sR[ i ] * sR[ i ] - w * w + 0.0 ) / 2.0 , l + 0.0 );
ln[ tCnt ].l = tL;
ln[ tCnt ].r = tR;
tCnt++;
}
}
n = tCnt;
}
Code: Select all
1 1000000001 100
1000000000 1000000000