Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:感谢前人铺垫~~~~~谁能帮我看看

Posted by yy17yy at 2010-11-09 12:53:18 on Problem 1328
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator