[UVA] 11800 - Determine the Shape
|
G |
Determine the Shape |
|
|
Input |
Standard Input |
|
|
Output |
Standard Output |
|
A toy
company recently found that toys like revolver, machine guns, fighting planes
are making children violent and destroying the peace of the world. The parents
also began to avoid these toys and inclined to educational toys. So they
decided to manufacture educational toys. One of these is a electric touch pad
on which children can put four points and the program will automatically join
the points to form a closed shape. Children will try to guess the shape and
when they press a button then it will automatically announce the shape. But
they are struggling to determine the shape and seek your help.
Your task is simple. You are given four points, no three of them are collinear, you have to output the simple polygonal shape formed by these points in the following order:
Square
Rectangle
Rhombus
Parallelogram
Trapezium
Ordinary Quadrilateral
For example if it is possible to form a square with the four points you must output ‘Square’, if it is not possible to form a square but possible to form a rectangle you must output ‘Rectangle’ and so on.
Input
Input starts with an integer T, the number of test cases (T≤50000). Each test case contains 4 lines. Each of the lines contains two space separated integers xi yi (-10000≤xi, yi≤ 10000) which are the coordinate values of a point.
Output
For each set of input output one line in the format “Case k: s”. Here k is the case number starting from 1 and s is the shape as described above. See sample input output for more details.
|
Sample Input |
Sample Output |
|
6 0 0 2 0 2 2 0 2 0 0 3 0 3 2 0 2 0 0 8 4 5 0 3 4 0 0 2 0 3 2 1 2 0 0 5 0 4 3 1 3 0 0 5 0 4 3 1 4
|
Case 1: Square Case 2: Rectangle Case 3: Rhombus Case 4: Parallelogram Case 5: Trapezium Case 6: Ordinary Quadrilateral
|
Note: If you have forgotten elementary geometry, here is the definitions to remind you:
Square: All sides are of
equal size all angles are 90o
Rectangle: Opposite sides are of equal size and all angles are 90o
Rhombus: All sides are of equal size but no angle is 90o
Parallelogram: Opposite sides are of equal size but no angle is 90o
Trapezium: Any two opposite sides are parallel but the other two is not.
Simple Polygon: Polygon having no self intersecting edge.
正方形：Square
矩形：Rectangle
菱形：Rhombus
平行四边形：Parallelogram
梯形：Trapezium
普通四边形：Ordinary Quadrilateral
考慮先做一次凸包，以免拉到對角線進行判斷。
接著判斷邊與邊之間的關係。
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
struct Pt {
long long x, y;
bool operator<(const Pt &a) const {
if(x != a.x)
return x < a.x;
return y < a.y;
}
Pt operator-(const Pt &a) {
Pt r;
r.x = x-a.x, r.y = y-a.y;
return r;
}
};
long long cross(Pt o, Pt a, Pt b) {
return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
int monotone(int n, Pt p[], Pt ch[]) {
sort(p, p+4);
int i, m = 0, 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-1;
}
long long dot(Pt a, Pt b) {
return a.x*b.x + a.y*b.y;
}
long long len(Pt a) {
return a.x*a.x + a.y*a.y;
}
int main() {
int testcase, cases = 0;
int i, j, k;
Pt D[50], CH[50];
scanf("%d", &testcase);
while(testcase--) {
for(i = 0; i < 4; i++)
scanf("%lld %lld", &D[i].x, &D[i].y);
int flag = monotone(4, D, CH);
Pt a, b, c, d;
Pt o;
o.x = o.y = 0;
a = CH[0], b = CH[1], c = CH[2], d = CH[3];
printf("Case %d: ", ++cases);
if(flag != 4) {
puts("Ordinary Quadrilateral");
continue;
}
if(dot(b-a, d-a) == 0 && dot(c-b, a-b) == 0 && dot(d-c, b-c) == 0) {
if(len(b-a) == len(c-b))
puts("Square");
else
puts("Rectangle");
} else if(len(b-a) == len(c-b) && len(b-a) == len(d-c) && len(b-a) == len(a-d))
puts("Rhombus");
else if(cross(o, b-a, c-d) == 0 && cross(o, c-b, d-a) == 0)
puts("Parallelogram");
else if(cross(o, b-a, c-d) == 0 || cross(o, c-b, d-a) == 0)
puts("Trapezium");
else
puts("Ordinary Quadrilateral");
}
return 0;
}