| ||||||||||
| 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 | |||||||||
测过很多组数据了 可是还是一直WA 过了的朋友们帮忙看看 精度应该没有问题#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
//const int MAXINT = 100000000;
//const double INF = 10e100;
//const double EPS = 10e-6;
const int maxn = 1010;
struct Line{double s, e;}l[maxn];
bool tag[maxn];
int ni, dis;
int tc;
int ans;
int cmp(const void * a, const void * b)
{
return ((*(Line *)a).s > (*(Line *)b).s) ? 1 : -1;
}
inline double len(int x, int y, double& x2)
{
x2 = x*1.0+sqrt(dis*dis-y*y);
return x*1.0-sqrt(dis*dis-y*y);
}
void init()
{
int i, x, y;
//initiation
memset(l, 0, sizeof(l));
memset(tag, false, sizeof(tag));
ans = 0;
//input
for(i=0; i<ni; i++)
{
scanf("%d%d", &x, &y);
if(y>dis) {ans = -1; return;}
l[i].s = len(x, y, l[i].e);
}
qsort(l, ni, sizeof(Line), cmp);
}
void work()
{
int i = 0, j;
if(ans != -1)
{
for(i=0; i<ni; i++)
if(!tag[i])
{
for(j=i+1; j<ni; j++)
{
//相交
if(l[j].s <= l[i].e && l[j].e >l[i].e) tag[j] = true;
//包含
if(l[j].e <= l[i].e) tag[i] = true;
}
if(!tag[i]) ans++;
}
}
printf("Case %d: %d\n", tc, ans);
}
int main()
{
// freopen("t.in", "r", stdin);
while(scanf("%d%d", &ni, &dis), ni>0)
{
tc++;
init();
work();
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator