| ||||||||||
| 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:AC代码附上 注意!!!!一定要注意左右交点的求解!!!要使用二元一次方程的求和公式求解左右交点,因为精度很重要!!!!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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator