10112 - Myacm Triangles
4427 단어 uva
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 (x1, y1), (x2, y2), and (x3, y3) is the absolute value of
0.5 × [(
y
3
-
y
1)(
x
2
-
x
1)
- (
y
2
-
y
1)(
x
3
-
x
1)].
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
제목: n 개의 점 이 있 고 세 개의 점 마다 삼각형 을 구성 할 수 있다.한 삼각형 에 경계 가 다른 점 을 포함 하지 않 을 때 요구 에 부합 되 는 삼각형 을 포함한다.조건 에 부합 되 는 모든 삼각형 중에서 면적 이 가장 큰 하 나 를 구하 고 하나만 확보 하 며 사전에 따라 이 삼각형 의 세 개의 정점 을 출력 한다.
우선 제목 에서 준 공식 에 대해 설명 을 한다.사실 포크 로.×삼각형 면적 의 합 은 a×b/2=|a|×|b|*sinA/2
그리고 점 이 삼각형 안에 있 는 지 아 닌 지 를 판단 하 는 것 이다. 나 는 특별히 좋 은 방법 을 생각해 내지 못 했다.아직 기하학 을 보기 시작 하지 도 않 았 다.그래서 면적 법 을 썼어 요.
점 이 삼각형 안에 있 으 면 경 계 를 포함한다 면.그러면 이 점 과 다른 세 점 중 임의의 두 점 으로 구 성 된 삼각형 의 합 은 이 삼각형 과 같 아야 한다.
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int x[20],y[20];
double area(int i, int j, int k)
{
double s;
s=0.5*((y[k]-y[i])*(x[j]-x[i])-(y[j]-y[i])*(x[k]-x[i]));
return fabs(s);
}
int main ()
{
int t,i,j,k,A,B,C,r;
double S=0,s;
char ch;
while(cin>>t)
{
S=0;
if (t==0) break;
for (i=1; i<=t; i++)
cin>>ch>>x[i]>>y[i];
for (i=1; i<=t-2; i++)
for (j=i+1; j<=t-1; j++)
for (k=j+1; k<=t; k++)
{
s=area(i,j,k);
if (s>S)
{
bool flag=true;
for (r=1; r<=t; r++)
if (r!=k && r!=i && r!=j)
{
if (s==area(i,j,r)+area(i,k,r)+area(j,k,r))
{
flag=false;
break;
}
}
if (flag)
{
S=s;
A=i;
B=j;
C=k;
}
}
}
printf("%c%c%c
",A+64,B+64,C+64);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
UVA - 10986 Sending email(Dijkstra 인접 테이블 + 우선 순위 대기열 최적화)제목 대의: s점에서 t점까지의 최소 거리를 구하는 그림을 주세요. 확인: 적나라한 최단길이지만 n이 너무 크면 인접 행렬을 사용할 수 없기 때문에 Dijkstra에 대한 인접표 + 우선 대기열 최적화가 필요합니다....
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.