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:AC代码附上 注意!!!!一定要注意左右交点的求解!!!要使用二元一次方程的求和公式求解左右交点,因为精度很重要!!!!

Posted by 20223465 at 2024-03-25 12:18:05 on Problem 1328
In Reply To:AC代码附上 注意!!!!一定要注意左右交点的求解!!!要使用二元一次方程的求和公式求解左右交点,因为精度很重要!!!! Posted by:ZHOUZUHAO at 2023-03-26 19:16:25
> //#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