UVa 10112 - Myacm Triangles

Table of Contents

• 1 题目
• 2 思路
• 3 代码
• 4 参考

1题目

=======================

Problem B: Myacm Triangles

Source file:	triangle.{c,cpp,java,pas}
Input file:	triangle.in
Output file:	triangle.out

There has been considerable archeological work on the ancient Myacm culture. Many artifacts have been found in what have been called power fields: a fairly small area, less than 100 meters square where there are from four to fifteen tall monuments with crystals on top. Such an area is mapped out above. Most of the artifacts discovered have come from inside a triangular area between just three of the monuments, now called the power triangle. After considerable analysis archeologists agree how this triangle is selected from all the triangles with three monuments as vertices: it is the triangle with the largest possible area that does not contain any other monuments inside the triangle or on an edge of the triangle. Each field contains only one such triangle.

Archeological teams are continuing to find more power fields. They would like to automate the task of locating the power triangles in power fields. Write a program that takes the positions of the monuments in any number of power fields as input and determines the power triangle for each power field.

A useful formula: the area of a triangle with vertices (x₁,y₁), (x₂,y₂), and (x₃,y₃) is the absolute value of

0.5 × [(y₃-y₁)(x₂-x₁)-(y₂-y₁)(x₃-x₁)].

For each power field there are several lines of data. The first line is the number of monuments: at least 4, and at most 15. For each monument there is a data line that starts with a one character label for the monument and is followed by the coordinates of the monument, which are nonnegative integers less than 100. The first label is A, and the next is B, and so on.

There is at least one such power field described. The end of input is indicated by a 0 for the number of monuments. The first sample data below corresponds to the diagram in the problem.

For each power field there is one line of output. It contains the three labels of the vertices of the power triangle, listed in increasing alphabetical order, with no spaces.

Example input:

6
A 1 0
B 4 0
C 0 3
D 1 3
E 4 4
F 0 6
4
A 0 0
B 1 0
C 99 0
D 99 99
0

Example output:

BEF
BCD

=======================

2思路

关键点有两个，一是已知四个点坐标，如何判断一个点是否在其他三点构成的三角形内部， 这个可以通过面积来计算。如果这个点和三角形三个边构成的三个小三角形面积和等于大 三角形的面积，那么此点在三角形内部。另一个关键点是如何找到面积最大的三角形，这个 我没有找到好的方法，用了四个循环，感觉好傻。。。

代码编写上需要注意下面几点：

• 注意计算面积时最后取绝对值
• 浮点数比较是否相等最好用EPS控制精度
• 使用scanf获取输入时，注意获取字符时回车的影响，需要用getchar()消除

3代码

/*
 * Problem: UVa 10112 - Myacm Triangles
 * Lang: ANSI C
 * Time: 0.009
 * Author: minix
 */

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

#define N 100
#define EPS 1e-8

typedef struct _Mount{
  char label;
  int x;
  int y;
}Mount;

Mount mounts[N];

/* get size of triangle (a,b,c) */
double get_area(Mount a, Mount b, Mount c) {
  return fabs(0.5 * ((c.y-a.y)*(b.x-a.x) - (b.y-a.y)*(c.x-a.x)));
}
 
/* whether triangle (a,b,c) contains point d or not */
int contains(Mount a, Mount b, Mount c, Mount d) {
  double sum = get_area(a,b,d) + get_area(a,c,d) + get_area(b,c,d);
  double gap = sum - get_area(a,b,c);
  return (fabs(gap) < EPS) ? 1: 0;
}

void solve(Mount mounts[], int n, char result[]) {
  int i, j, k, s;
  double max = 0;

  for (i=0; i<n; i++)
    for (j=0; j<n; j++) {
      if (j == i) continue;
      for (k=0; k<n; k++) {
        if (k == j || k == i) continue;
        for (s=0; s<n; s++) {
          if (s == i || s == j || s == k)
            continue;
          if (contains(mounts[i], mounts[j], mounts[k], mounts[s]) == 1)
            break;
        }

        /* get max area */
        if ((s == n) && get_area(mounts[i], mounts[j], mounts[k]) > max) {
          max = get_area(mounts[i], mounts[j], mounts[k]);
          result[0] = mounts[i].label;
          result[1] = mounts[j].label;
          result[2] = mounts[k].label;
        }
      }
    }
  result[3] = '\0';
}

int cmp(const void *s, const void *t) {
  return *((char *)s) - *((char *)t);
}

int main() {
  int n, i;
  char result[4];

  while (1) {
    scanf ("%d", &n);
    if (n == 0)
      break;
    getchar(); /* read '\n' */

    for (i=0; i<n; i++) {
      scanf ("%c%d%d", &mounts[i].label, &mounts[i].x, &mounts[i].y);
      getchar();
    }

    solve (mounts, n, result);
    qsort (result, 3, sizeof(char), cmp);
    printf ("%s\n", result);

  }

  return 0;
}

4参考

1http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=101&problem=1053

2 刘汝佳，算法竞赛入门经典，p84-85