OJ Board

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

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;
			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

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