| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Presentation Error的吐血了贡献了无数的Presentation Error,调的心都要碎了
一定要注意输出格式啊。。。。。。。
#include<iostream>
#include<Cstdio>
#include <algorithm>
#include<Cmath>
#include<Cstring>
using namespace std;
struct Node
{
double a1, a2;
};
Node pos[1001];
bool used[1001];
void ShellSort(Node array[],int length)
{
int d = length/2; //设置希尔排序的增量
int i ;
int j;
Node temp;
while(d>=1)
{
for(i=d;i<length;i++)
{
temp=array[i];
j=i-d;
while(j>=0 && array[j].a2> temp.a2)
{
array[j+d]=array[j];
j=j-d;
}
array[j+d] = temp;
}
d= d/2; //缩小增量
}
}
int Check(Node array[],int length)
{
int size = 0, index;
double min;
memset(used, false, length);
while (1)
{
for(int i = 0; i < length; ++i)
{
if(!used[i])
{
min = array[i].a2 + 0.000001;
index = i;
break;
}
}
//cout << "Min is"<<min << endl;
bool flag = true;
for(int i = 0; i < length; ++i)
{
if(!used[i] && array[i].a1 < min)
{
used[i] = true;
}
flag &= used[i];
//cout << used[i] << endl;
}
size++;
if(flag)
return size;
}
return -1;
}
int main()
{
int n, i, ans, size, num = 1, count;
double x, y, d, temp;
bool flag;
while (1)
{
cin >> n >> d;
if(n == 0 && d == 0)
break;
count = 0;
flag = true;
for(i = 0; i < n; ++i)
{
cin >> x >> y;
if(d > 0 && d*d-y*y >= -0.00000001)
{
pos[count].a1 = x - sqrt(d*d-y*y);
pos[count].a2 = x + sqrt(d*d-y*y);
count ++;
}
else
{
flag = false;
}
}
if(flag)
{
ShellSort(pos, count);
// for(int i = 0; i < count; ++i)
// cout << pos[i].a1 << " " << pos[i].a2 << endl;
size = Check(pos, count);
cout << "Case "<<num << ": " << size << endl;
num ++;
}
else
{
cout << "Case "<<num << ": " << -1 << endl;
num ++;
}
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator