牛客contest5668-C

传送门

题目大意

按顺时针或逆时针顺序给出n个端点的平面坐标，它们组成一个形如下图的二维几何图形，

判断这个图形是右手形还是左手形。图形可以被旋转但不能被缩放。

思路

题设中提到图形的大小不会被改变，也就是说即使所给出的点不同，但他们之间的相对大小是绝对地，可以从这个关系入手。

可以看见，图示中最长边就是底边，它的长度是9，而大拇指是一条紧挨着它且长度为6的边，小拇指则为8。

那么可以去找相邻的3个点，如果找到长度为9的边，就去验证是否存在长度为6或8的相邻边。因为方向不确定，所以使用向量积来判断，向量积大于0时验证大拇指，反之验证小拇指。

具体地，因为题中数据均为浮点数，所以计算距离时存在小数点的精度问题。而例图中的长度均是整数。这里采用忽略小数位的方法来近似判等，即用计算所得的距离值-目标距离值，如果所得差小于一个极小数e，那么则判二者相等。

#include <bits/stdc++.h>

using namespace std;

const double E = 1e-5;
const int LIM = 20;

struct node
{
	double x, y;
} a[30];

int	t;
bool isLeft;

double dis( node x, node y )
{
	return sqrt( (x.x - y.x) * (x.x - y.x) + (x.y - y.y) * (x.y - y.y) );
}

double vec( node x, node y, node z )
{
	return (y.x - x.x) * (z.y - x.y) - (y.y - x.y) * (z.x - y.x);
}

int main()
{
	scanf( "%d", &t );
	while ( t-- )
	{
		isLeft = 0;
		for ( int i = 0; i < LIM; i++ )
			scanf( "%lf%lf", &a[i].x, &a[i].y );
		
		for ( int i = 0; i < LIM; i++ )
			if ( fabs( dis( a[i], a[(i + 1) % LIM] ) - 9 ) < E )
			{
				node x = a[i];
				node y = a[(i + 1) % LIM];
				node z = a[(i + 2) % LIM];
				if ( vec( x, y, z ) > 0 && fabs( dis( y, z ) - 6 ) < E || vec( x, y, z ) < 0 && fabs( dis( y, z ) - 8 ) < E )
					isLeft = 1;
				break;
			}

		if ( isLeft ) puts("left");
		else puts("right");
	}
	return 0;
}