北京网站优化托管,wap自助建站模块,wordpress评论跳过验证码,景区网站建设材料题目大意#xff1a;给出n个点的编号和坐标#xff0c;按逆时针方向连接着n个点#xff0c;按连接的先后顺序输出每个点的编号。 题目思路#xff1a;Cross#xff08;a,b#xff09;表示a,b的叉积#xff0c;若小于0#xff1a;a在b的逆时针方向#xff0c;若大于0a在…题目大意给出n个点的编号和坐标按逆时针方向连接着n个点按连接的先后顺序输出每个点的编号。 题目思路Crossa,b表示a,b的叉积若小于0a在b的逆时针方向若大于0a在b的顺时针方向。每次都sort一下找出在当前点逆时针方向的最远的点。数据很小O(N*N*logN)的复杂度0s AC了…… #includecstdio
#includecstdlib
#includecmath
#includeiostream
#includealgorithm
#includecstring
#includevector
#includequeue
#define INF 0x3f3f3f3f
#define MAX 100005using namespace std;int n,pos,ans[MAX];struct node
{int id,x,y;
}point[MAX];int Dist(int x1,int y1,int x2,int y2)
{return sqrt((x1-x2)*(x1-x2)*1.0 (y1-y2)*(y1-y2)*1.0);
}int Cross(int x1,int y1,int x2,int y2,int x3,int y3)
{return (x1-x2)*(y1-y3)-(x1-x3)*(y1-y2);
}bool cmp(struct node A,struct node B)
{int opCross(point[pos].x,point[pos].y,A.x,A.y,B.x,B.y);if(op0)return true;else if(op0 Dist(point[pos].x,point[pos].y,A.x,A.y)Dist(point[pos].x,point[pos].y,B.x,B.y))return true;return false;
}int main()
{int T,cnt;scanf(%d,T);while(T--){pos0;cnt0;memset(ans,0,sizeof(ans));scanf(%d,n);scanf(%d%d%d,point[0].id,point[0].x,point[0].y);for(int i1;in;i){scanf(%d%d%d,point[i].id,point[i].x,point[i].y);if(point[i].y point[0].y)//找出起点左下方的点swap(point[0],point[i]);else if(point[i].ypoint[0].y point[i].x point[0].x)swap(point[0],point[i]);}sort(point,pointn,cmp);ans[cnt]point[pos].id;for(int i1;in;i){sort(pointi,pointn,cmp);ans[cnt]point[pos].id;}printf(%d ,cnt);for(int i0;icnt;i)printf(%d%c,ans[i],icnt-1?\n: );}return 0;
} View Code 转载于:https://www.cnblogs.com/alan-W/p/6019998.html
