学步园

纠结了很长时间，决定还是不写这个题目了，HOJ的过了，POJ一直WA，估计就是精度问题了，这个贪心思维挺会，精度控制就很无脑了，决定放弃这个题目，贴出来HOJ 1052的代码。

 

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <limits.h>
#include <map>
#include <cmath>
#include <set>
#define FOPEN freopen("D:\\1.txt","r",stdin);
#define MAXN 5005

using namespace std;

int n,m;
typedef struct pair<int,int> PII;
struct compare{

bool operator ()(PII a,PII b) {
if(a.second == b.second)
return a.first < b.first;
return a.second < b.second;
        }
};

multiset<PII,compare> mset;
multiset<PII,compare>::iterator p;
int f_oper(int x,int y) {
return -(int)sqrt((double)m*m - y*y) + x;
}
int S_oper(int x,int y) {
return (int)sqrt((double)m*m - y*y) + x;
}


int main() {
//FOPEN
        int a,b;
int kk = 1;
while(~scanf("%d%d",&n,&m)) {
if(n==0 && m==0) break;
int flag = 0;
                mset.clear();
for(int i= 0;i<n;i++) {
                        scanf("%d%d",&a,&b);
if(abs(b) > m) {
                                flag = 1;
break;
                        } else {
                                mset.insert(make_pair(f_oper(a,b),S_oper(a,b)));
                        }
                }
/*mset.insert(make_pair(1,3));
                mset.insert(make_pair(2,4));
                mset.insert(make_pair(4,5));
                mset.insert(make_pair(5,8));
                mset.insert(make_pair(6,7));
                mset.insert(make_pair(7,9));
                mset.insert(make_pair(8,11));*/
//for(p = mset.begin();p!=mset.end();p++) {
//      cout<<p->first<<" "<<p->second<<endl;
//}
                if(flag) {
                        printf("Case %d: -1\n",kk++);
                } else {
int tmp=0;
                        p = mset.begin();
int up = p->second;
//cout<<p->first<<" "<<p->second<<endl;
                        while(p != mset.end()) {
                                tmp++;
while(p->first <= up && p != mset.end()) p++;
//p = mset.upper_bound(make_pair(p->second,p->second));
//cout<<p->first<<" - "<<p->second<<endl;
                                up = p->second;
//cout<<up<<endl;
                        }
                        printf("Case %d: %d\n",kk++,tmp);
                }
        }
}