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

AC代码附上 注意!!!!一定要注意左右交点的求解!!!要使用二元一次方程的求和公式求解左右交点,因为精度很重要!!!!

Posted by ZHOUZUHAO at 2023-03-26 19:16:25 on Problem 1328
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
int n,d;
int x,y;
int num=0,ans,flag;
const int maxn=1005;
typedef double db;
typedef pair<db,db> pdd;
pdd ils[maxn];
bool cmp(pdd a,pdd b){
	if(a.first!=b.first) return a.first<b.first;
	else return a.second>b.second;
}
void solve(){
	if(flag){
		printf("Case %d: -1\n",num);
		//cout<<"Case "<<num<<": -1"<<'\n';
		return;
	}
	sort(ils+1,ils+1+n,cmp);
	db nowl,nowr,nextl,nextr;
	nowl=ils[1].first;
	nowr=ils[1].second;
	ans++;
	for(int i=2;i<=n;i++){
		nextl=ils[i].first;
		nextr=ils[i].second;
		if(nextl>nowr){
			nowl=nextl,nowr=nextr;
			ans++;
		}
		else{
			nowl=max(nowl,nextl);
			nowr=min(nowr,nextr);
		}
	}
	printf("Case %d: %d\n",num,ans);
	//cout<<"Case "<<num<<": "<<ans<<'\n';
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	while(cin>>n>>d&&(n||d)){
		num++;
		flag=ans=0;
		for(int i=1;i<=n;i++){
			cin>>x>>y;
			db a,b,c;
			a=1;b=-2*x;c=x*x+y*y-d*d;
			ils[i].first=(-b-sqrt(b*b-4*a*c))/2*a;
			ils[i].second=(-b+sqrt(b*b-4*a*c))/2*a;
			if((b*b-4*a*c)<0||d<=0||y<0) flag=1;
		}
		solve();
	}
	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