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