OJ Board

Code: Select all

{$S-,R-}

program UVA10382;

const
	maxn	=	10000;

type
	tseg	=	record
				l , r	:	double;
			end;

var
	seg	:	array [ 1 .. maxn ] of tseg;
	w , l	:	double;
	n	:	integer;
	tot	:	integer;
	ans	:	integer;

procedure init;
    var
	i	:	integer;
	p , r	:	double;
	len	:	double;
    begin
	read ( n , l , w );
	tot := 0;
	for i := 1 to n do
	begin
		read ( p , r );
		if r * 2 > w then
		begin
			inc ( tot );
			len := sqrt ( sqr ( r ) - sqr ( w / 2 ) );
			seg [ tot ] . l := p - len ;
			seg [ tot ] . r := p + len ;
		end;
	end;
    end;

function pre ( a , b : tseg ) : boolean;
    begin
	if a . l < b . l then pre := true else
	if a . l > b . l then pre := false else
	if a . r > b . r then pre := true else pre := false;
    end;

procedure swap ( var a , b : tseg );
    var
	c	:	tseg;
    begin
	c := a ; a := b ; b := c;
    end;

procedure sort ( h , t : integer );
    var
	i , j	:	integer;
	x	:	tseg;
    begin
	if h >= t then exit;
	i := h ; j := t;
	x := seg [ ( h + t ) shr 1 ];
	repeat
		while pre ( seg [ i ] , x ) do inc ( i );
		while pre ( x , seg [ j ] ) do dec ( j );
		if i <= j then
		begin
			swap ( seg [ i ] , seg [ j ] );
			inc ( i ) ; dec ( j );
		end;
	until i > j;
	sort ( h , j );
	sort ( i , t );
    end;

procedure prepare;
    var
	i , j	:	integer;
    begin
	n := tot;
	tot := 0;
	i := 1;
	while i <= n do
	begin
		inc ( tot );
		seg [ tot ] := seg [ i ];
		j := i + 1;
		while ( j <= n ) and ( seg [ j ] . r <= seg [ i ] . r ) do inc ( j );
		i := j;
	end;
    end;

procedure greedy;
    var
	i , j	:	integer;
	x	:	integer;
    begin
	ans := -1;
	if tot = 0 then exit;
	if seg [ 1 ] . l > 0 then exit;
	if seg [ tot ] . r < l then exit;
	i := tot;
	while ( i > 1 ) and ( seg [ i ] . l > 0 ) do dec ( i );
	x := 1;
	while ( i < tot ) and ( seg [ i ] . r < l ) do
	begin
		j := i + 1;
		while ( j <= tot ) and ( seg [ i ] . r >= seg [ j ] . l ) do inc ( j );
		dec ( j );
		if j = i then exit;
		inc ( x );
		i := j;
	end;
	ans := x;
    end;

begin
	repeat
		init;
		sort ( 1 , tot );
		prepare;
		greedy;
		writeln ( ans );
		while not eof ( input ) and eoln ( input ) do readln;
	until eof ( input );
end.

Code: Select all

11 27 3
1 17
2 18
8 1
6 7
2 3
3 7
12 11
16 16
4 4
12 13
16 18
1 6 26
11 11
15 22 16
3 4
5 13
1 12
18 19
2 15
12 1
11 19
8 10
12 11
7 16
12 2
9 16
6 8
9 6
7 14
11 16 7
2 19
3 10
15 15
5 14
5 7
20 16
4 15
2 7
11 17
1 10
11 19
13 25 9
4 17
19 16
8 11
19 18
6 1
13 12
11 8
11 2
1 11
11 18
20 5
15 14
6 13
11 23 4
15 9
3 10
3 9
17 14
3 20
17 5
13 13
18 14
13 3
17 16
13 18

Code: Select all

1
-1
1
1
1
1

Code: Select all

#include <math.h> 
#include <algorithm> 
#include <iostream> 
using namespace std; 
struct circle 
{ 
bool mark; 
int radius; 
int position; 
long double left; 
long double right; 
void setRectangle(int ,int); 
}; 
void circle::setRectangle(int w,int l) 
{ 
long double temp ; 
if(radius > w / 2.0 ) 
temp = sqrt(((long double)(radius * radius) - (long double)((w * w)/4.0 ))); 
else 
{ 
temp = 0.0; 
} 
left = position - temp; 
if(left < 0.0) 
left = 0.0; 
right = position + temp; 
if(right > l) 
right = l; 
} 
bool operator<(const circle &a, const circle &b) 
{ 
return (a.left < b.left); 
} 
circle data [10001]; 
int main() 
{ 
int n,w,l,counter,index; 
double leftBound,rightBound; 
bool find ; 
while(cin>>n>>l>>w) 
{ 
for(int i=0;i<n;i++) 
{ 
cin>>data[i].position>>data[i].radius; 
data[i].setRectangle(w,l); 
} 
sort(data,data + n); 
leftBound = rightBound = 0; 
index = counter = 0; 
while(leftBound != l) 
{ 
find = false; 
for(int i=index;i<n;i++) 
{ 
if(data[i].left<=leftBound && data[i].right > rightBound ) 
{ 
index = i; 
rightBound = data[i].right; 
find = true; 
} 
} 
if(!find) 
break; 
counter ++; 
leftBound = data[index].right; 

} 
if(find) 
cout<<counter<<endl; 
else 
cout<<-1<<endl; 
} 
return 0; 
}

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(&section[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;
			while (section[++p].begin <= st)
				if (section[p].end - st > tmpmax)
				{
					tmpmax = section[p].end - st;
					maxi = p;
				}
			if (maxi == p)
			{
				cout << "-1\n";
				st = l;
				count = -1;
			}
			else
			{
				st = section[maxi].end;
				count++;
			}
		}
		if (count > 0)
			cout << count << endl;
	}
	return 0;
}