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