| ||||||||||
| 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