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 |
Re:感谢前人铺垫~~~~~谁能帮我看看In Reply To:感谢前人铺垫~~~~~ Posted by:jcf at 2010-08-21 16:00:40 > 发帖的大牛们,谢谢了,看了你们写的一些注意事项,一次AC > > > 写一下我的思路吧 > 先做出每个点的区间 > qj[i].l qj[i].r > 按r进行排序 > 然后开始贪心: > 设置一个lastpoint变量,记录上一个点的位置(初值为负无穷) > 循环判断 > 如果lastpoint<l,则雷达数加1,修改lastpoint为r > > 中途注意判断是否成立,否则输出雷达数-1 郁闷,,,不知道怎么回事,,,我还是WA,总WA啊,,不想再看了,,,谁能帮我看看??? #include <iostream> #include <algorithm> #include <vector> #include <cmath> using namespace std; int main() { vector<pair<double,double> >v; int n; double d; int k=0; while(cin>>n>>d&&n) { v.clear(); bool stop=false; int i; for(i=0;i<n;i++) { double x,y; cin>>x>>y; if(stop) continue; if(y>d||y<0) { stop=true; continue; } v.push_back(pair<double,double>(x-sqrt((double)(d*d-y*y)),x+sqrt((double)(d*d-y*y)))); } if(stop) { cout<<"Case "<<++k<<": -1"<<endl; continue; } stable_sort(v.begin(),v.end()); int num=1; int right=v[0].second; for(i=1;i<v.size();i++) { if(v[i].first>right) { num++; right=v[i].second; } } cout<<"Case "<<++k<<": "<<num<<endl; } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator