题目大意:给你20个点,按照顺时针方向或者逆时针方向给出,如下图(该图为右掌):
它可以旋转和平移。然后问你给出的手掌是左还是右。
输入
1 19.471068 -6.709056 13.814214 -1.052201 13.107107 -1.759308 15.228427 -3.880629 14.521320 -4.587735 10.985786 -1.052201 10.278680 -1.759308 13.814214 -5.294842 13.107107 -6.001949 9.571573 -2.466415 8.864466 -3.173522 12.400000 -6.709056 11.692893 -7.416162 8.157359 -3.880629 7.450253 -4.587735 12.400000 -9.537483 11.692893 -10.244590 9.571573 -8.123269 8.864466 -8.830376 13.107107 -13.073017
输出
right
emmm,最简单直接的办法就是找特殊的边,我们注意到大拇指的那条边和最底下的那条边的长度是唯一的,那么我们就可以直接通过这连续的三点来判断边6到边9是顺时针还是逆时针的。这个判断我们可以借助向量的叉积来搞,具体可以百度3个点判断顺逆时针方向。至于精度的话得注意一下,出题人可能卡了精度,对于都是整数的边,我们可以适当的将精度放宽些,就算是将esp设置为0.01也没什么关系。
以下是AC代码:
#include <bits/stdc++.h> using namespace std; const double esp=1e-5; struct node { double x,y; node operator -(const node &a)const{ return node{x-a.x,y-a.y}; } double operator *(const node &a)const{ return x*a.y-y*a.x; } }p[50]; double pw(double x) {return x*x;} double dist(node a,node b) { return sqrt(pw(a.x-b.x)+pw(a.y-b.y)); } int clock_dir(node a,node b,node c) { node ab=b-a,bc=c-b; return (ab*bc)<0?1:0; } int main(int argc, char const *argv[]) { int t; scanf ("%d",&t); while (t--){ double x,y; int n=20; for (int i=1; i<=n; i++){ scanf ("%lf%lf",&x,&y); p[i]=node{x,y}; } p[n+1]=p[1],p[n+2]=p[2]; int mark=0; for (int i=1; i<=n; i++){ if (fabs(dist(p[i+1],p[i])-6)<esp && fabs(dist(p[i+2],p[i+1])-9)<esp && !clock_dir(p[i],p[i+1],p[i+2])) mark=1; if (fabs(dist(p[i],p[i+1])-9)<esp && fabs(dist(p[i+2],p[i+1])-6)<esp && clock_dir(p[i],p[i+1],p[i+2])) mark=1; } if (mark) printf("right "); else printf("left "); } return 0; }