Triangular Vertices

Consider the points on an infinite grid of equilateral triangles as shown below:

Note that if we number the points from left to right and top to bottom, then groups of these points form the vertices of certain geometric shapes. For example, the sets of points {1,2,3} and {7,9,18} are the vertices of triangles, the sets {11,13,26,24} and {2,7,9,18} are the vertices of parallelograms, and the sets {4,5,9,13,12,7} and {8,10,17,21,32,34} are the vertices of hexagons.

Write a program which will repeatedly accept a set of points on this triangular grid, analyze it, and determine whether the points are the vertices of one of the following ``acceptable" figures: triangle, parallelogram, or hexagon. In order for a figure to be acceptable, it must meet the following two conditions:

 1) Each side of the figure must coincide with an edge in the grid. 
 and 2) All sides of the figure must be of the same length. 
 

Input

The input will consist of an unknown number of point sets. Each point set will appear on a separate line in the file. There are at most six points in a set and the points are limited to the range 1..32767.

Output

For each point set in the input file, your program should deduce from the number of points in the set which geometric figure the set potentially represents; e.g., six points can only represent a hexagon, etc. The output must be a series of lines listing each point set followed by the results of your analysis.

Sample Input

1 2 3 11 13 29 31 26 11 13 24 4 5 9 13 12 7 1 2 3 4 5 47 11 13 23 25

Sample Output

1 2 3 are the vertices of a triangle 11 13 29 31 are not the vertices of an acceptable figure 26 11 13 24 are the vertices of a parallelogram 4 5 9 13 12 7 are the vertices of a hexagon 1 2 3 4 5 are not the vertices of an acceptable figure 47 are not the vertices of an acceptable figure 11 13 23 25 are not the vertices of an acceptable figure

#include <stdio.h>
#include <math.h>
#include <sstream>
#include <algorithm>
#define eps 1e-6
using namespace std;
double trix[32768], triy[32768];
const double pi = acos(-1);
struct Pt {
 double x, y;
};
bool cmp(Pt a, Pt b) {
 if(a.x != b.x)
 return a.x < b.x;
 return a.y < b.y;
}
double cross(Pt o, Pt a, Pt b) {
 return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
double dist(Pt a, Pt b) {
 return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
Pt P[1000], CH[1000];
int convex(int n) {
 sort(P, P+n, cmp);
 int m = 0, i, t;
 for(i = 0; i < n;i++) {
 while(m >= 2 && cross(CH[m-2], CH[m-1], P[i]) <= 0)
 m--;
 CH[m++] = P[i];
 }
 for(i = n-1, t = m+1; i >= 0; i--) {
 while(m >= t && cross(CH[m-2], CH[m-1], P[i]) <= 0)
 m--;
 CH[m++] = P[i];
 }
 return m;
}
int main() {
 trix[1] = triy[1] = 0;
 double disy = sqrt(3)/2;
 int i, j, idx = 2, x;
 char buf[1024];
 for(i = 2; idx < 32768;i++) {
 trix[idx] = trix[idx-i+1]-0.5;
 triy[idx] = triy[idx-i+1]-disy;
 for(j = 1, idx++; j < i && idx < 32768; j++, idx++) {
 trix[idx] = trix[idx-1]+1;
 triy[idx] = triy[idx-1];
 }
 }
 while(gets(buf)) {
 stringstream sin(buf);
 int n = 0, m;
 while(sin >> x) {
 P[n].x = trix[x];
 P[n].y = triy[x];
 n++;
 }
 sort(P, P+n, cmp);
 m = convex(n);
 printf("%s ", buf);
 if(m-1 != n || n == 1 || m-1 == 5) {
 puts("are not the vertices of an acceptable figure");
 continue;
 }
 double tmp = dist(CH[0], CH[1]);
 for(i = 1; i < m; i++) { // check all sides must be of the same length.
 if(fabs(dist(CH[i], CH[i-1])-tmp) > eps)
 break;
 }
 if(i != m) {
 puts("are not the vertices of an acceptable figure");
 continue;
 }
 for(i = 1; i < m-1; i++) { // check each side must coincide with an edge in the grid.
 tmp = fabs(cross(CH[i], CH[i-1], CH[i+1]));
 if(fabs(asin(tmp/sqrt(dist(CH[i], CH[i-1]))/sqrt(dist(CH[i], CH[i+1])))*180/pi - 60) > eps)
 break;
 }
 if(i != m-1) {
 puts("are not the vertices of an acceptable figure");
 continue;
 }
 printf("are the vertices of ");
 if(n == 3)
 puts("a triangle");
 else if(n == 4)
 puts("a parallelogram");
 else
 puts("a hexagon");
 }
 return 0;
}

您可能以下文章有趣

[UVA][math] 10466 - How Far?

[UVA][bfs] 10477 - The Hybrid Knight

[UVA] 858 - Berry Picking

[UVA] 12047 - Highest Paid Toll