7.8寻找maxima
#include<iostream>#include<vector>#include<algorithm>using namespace std;const int maxn=100005;int n; struct data{int x,y;}a[maxn];bool cmp(data a,data b){return a.x<b.x||(a.x==b.x&&a.y<b.y);}bool mark[maxn];int main(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i].x>>a[i].y;}sort(a+1,a+n+1,cmp);int MAX=-1;for(int i=n;i>=1;i--){if(a[i].y>MAX){mark[i]=1;MAX=a[i].y; }}for(int i=1;i<=n;i++){if(mark[i]){cout<<"("<<a[i].x<<","<<a[i].y<<")"<<endl; } }return 0;}
7.11 寻找最近点对
洛谷P1257 平面上的最接近点对
#include<iostream>#include<vector>#include<cmath>#include<algorithm>using namespace std;#define INF 0x3f3f3f3f const int maxn=10005;struct point{int x,y;}p[maxn]; double dist(point a,point b){return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));}bool cmp1(point a,point b){return a.x<b.x||(a.x==b.x&&a.y<b.y);}bool cmp2(point a,point b){return a.y<b.y; }double solve(int l,int r){int mid=(l+r)>>1;if(l==r){return INF;}if(l+1==r){return dist(p[l],p[r]);}double d=min(solve(l,mid),solve(mid+1,r));vector<point>v; for(int i=l;i<=r;i++){if(fabs(p[i].x-p[mid].x)<=d){v.push_back(p[i]); }}sort(v.begin(),v.end(),cmp2);for(int i=0;i<=v.size()-1;i++){for(int j=i+1;j<=v.size()-1;j++){if(v[j].y-v[i].y<d){d=min(d,dist(v[i],v[j]));}}}return d;} int main(){int n;cin>>n;for(int i=1;i<=n;i++){cin>>p[i].x>>p[i].y; }sort(p+1,p+n+1,cmp1);double ans=solve(1,n);printf("%.4f\n",ans);}
