做空比特币网站/今日新闻联播

A - Convex Hull（凸包极角排序）

Online Judge

需要注意这里的排序要求相同角度优先选远的，但是一般是优先选近的，我也不知道为啥，先记着吧。

#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-7;
const int maxn = 100005;
struct node{double x, y;} p[maxn];
int t, n, cnt;
double check(node a1,node a2,node b1,node b2){//检查叉积是否大于0，如果是a就逆时针转到b return (a2.x-a1.x)*(b2.y-b1.y)-(b2.x-b1.x)*(a2.y-a1.y);
}
double d(node p1,node p2){ //计算两点间距离return sqrt((p2.y-p1.y)*(p2.y-p1.y)+(p2.x-p1.x)*(p2.x-p1.x));
}
bool cmp(node p1,node p2){ //排序函数double tmp=check(p[1],p1,p[1],p2);if(abs(tmp)<eps && d(p[0],p1)>d(p[0],p2)) return 1; //角度相同，取近的点if(tmp>0) return 1;return 0;
}
int main(){cin>>t;while(t--){cin>>n; cnt = 0;int a, b; char ch; double mid;for(int i=1; i<=n; i++){cin>>a>>b>>ch;if(ch=='N') continue; //跳过非顶点p[++cnt].x = a; p[cnt].y = b;if(cnt!=1&&(p[cnt].x<p[1].x || (p[cnt].x==p[1].x && p[cnt].y<p[1].y))){//找到x最小同时y最小的点mid=p[1].y;p[1].y=p[cnt].y;p[cnt].y=mid;mid=p[1].x;p[1].x=p[cnt].x;p[cnt].x=mid;}}sort(p+2,p+1+cnt,cmp);printf("%d\n",cnt);for(int i=1; i<=cnt; i++) {printf("%d %d\n",(int)p[i].x,(int)p[i].y);}}
}

F - Beauty Contest（旋转卡壳，获取最大直径模板）

[USACO03FALL]Beauty Contest G /【模板】旋转卡壳 - 洛谷

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
struct node {double x,y;} p[maxn], s[maxn];
node operator-(node a,node b) {return(node){a.x-b.x,a.y-b.y};}
double dist(node a,node b){return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}
double cross(node a,node b){return a.x*b.y-a.y*b.x;}
int n,top,my=1;
double ans;
bool cmp(node a,node b){double t1=atan2(a.y-p[1].y,a.x-p[1].x);double t2=atan2(b.y-p[1].y, b.x-p[1].x);return t1==t2?a.x<b.x:t1<t2; //相同角度，近的排前面
}
void gettb(){ //生成凸包for(int i=1;i<=n;i++){scanf("%lf%lf",&p[i].x,&p[i].y); //输入点坐标if(p[i].y<p[my].y || (p[i].y==p[my].y && p[i].x<p[my].x)) my=i; //找最小点位置}swap(p[1],p[my]); //把最小点放第一位sort(p+2,p+n+1,cmp); //按极角序排序s[++top]=p[1];for(int i=2;i<=n;i++){while(top>1 && cross(s[top]-s[top-1],p[i]-s[top])<=0) top--; //当遇到不是逆时针转，说明不是凸包，弹栈s[++top]=p[i]; //当前点入栈}s[top+1]=p[1]; //特殊的一步，闭合凸包
}
void getmxd(){ //旋转卡壳，获取最大直径if(top==2){ //特判只有两个点的情况printf("%.0f\n",dist(s[1],s[2]));return;}int T=3; //当前顶点for(int i=1;i<=top;i++){while(cross(s[i+1]-s[i],s[T]-s[i])<=cross(s[i+1]-s[i],s[T+1]-s[i])) T=T%top+1;ans=max(ans,max(dist(s[i],s[T]),dist(s[i+1],s[T]))); } printf("%.0f\n",ans);
}
int main(){scanf("%d",&n);gettb();getmxd();
}