15. Smallest Triangle

<설명>

좌표 평면의 점 N개를 입력으로 받아서, 그 점들로 만들 수 있는 삼각형 중 가장 넓이가 작은 것을 출력한다.

<Input>

첫번째 입력: 하나의 정수 N [3,250]

두번째 입력: [-10000, 10000] 사이에 있는 두 정수 x, y

<Output>

만들 수 있는 삼각형 중 최소 넓이

<소스코드>

#include <stdio.h>
#include <math.h>
 
int main (void)
    {
        int N,n;
        int i,j,k;
        double cS;
        double min=100000000;
        
        scanf("%d",&N);
        int x[N-1];
        int y[N-1];
        
        for(i=0;i<N;i++){
            scanf("%d %d",&x[i],&y[i]);
        }
        for(i=0;i<N-2;i++){
            for(j=i+1;j<N-1;j++){
                for(k=j+1;k<N;k++){
                  cS=(double)abs(((x[i]*y[j])+(x[j]*y[k])+(x[k]*y[i]))-((x[j]*y[i])+(x[k]*y[j])+(x[i]*y[k])))/2.;
                    
                  if(min>cS&&cS!=0)
                      min=cS;
                }
            }
        }
        printf("%lf",min);
        return 0;
    }

<설명>

점의 좌표가 주어졌을 때 삼각형의 넓이를 구할 수 있는 공식을 활용한다.

넓이가 0인 것은 삼각형이 아니기 때문에, 넓이가 0인 도형은 제외한다.