CodeChef: Find Area of Triangles


The problem

:

Lira is a little girl form Bytenicut, a small and cozy village located in the country of Byteland.

As the village is located on a somewhat hidden and isolated area, little Lira is a bit lonely and she needs to invent new games that she can play for herself.

However, Lira is also very clever, so, she already invented a new game.
She has many stones with her, which she will display on groups of three stones on the ground on a triangle like shape and then, she will select two triangles, one with the smallest area and one with the largest area as the most beautiful ones.

While it’s easy for Lira to “estimate” the areas of the triangles by their relative sizes, it’s harder for her to actually calculate these areas.
But, it turns out, that Lira is also friends with YOU, an exceptional Mathematics student, and she knew that you would know exactly how to do such verification.

Lira also numbered the triangles from 1 to N, and now she wants to know the indices of the triangles with the smallest and largest area respectively.
It is now up to you, to help Lira and calculate the areas of the triangles and output their numbers.

Input

The first line of the input file contains an integer, N, denoting the number of triangles on the given input file.

Then N lines follow, each line containing six space-separated integers, denoting the coordinates x1, y1, x2, y2, x3, y3

Output

You should output two space separated integers, the indexes of the triangles with the smallest and largest area, respectively.

If there are multiple triangles with the same area, then the last index should be printed.

Constraints

2 ≤ N ≤ 100
-1000 ≤ xi, yi ≤ 1000

Example

Input:
2
0 0 0 100 100 0
1 1 1 5 5 1

Output:
2 1

My Solution

#include <stdio.h>

float findArea(int arr[6]){
  float value;

  value = (arr[0]*(arr[3]-arr[5])) + (arr[2] * (arr[5] - arr[1])) + (arr[4]*(arr[1] - arr[3]));
  value /= 2;
  if(value<0)
    value *= -1;

  return value;

}

int main(){
  int N;
  int i,j;
  int tri[100][6];
  int smallId, largeId;
  float  smallValue,largeValue;
  float  temp;

  scanf("%d",&N);
  
  for(i=0;i<N;i++){
    for(j=0;j<6;j++)
      scanf("%d",&tri[i][j]);
  }

  smallId = 0; largeId = 0;
  temp = findArea(tri[0]);
//  printf("first area=%f\n",temp);

  smallValue = largeValue = temp; 

  for (i=1;i<N;i++){
    temp = findArea(tri[i]);
//    printf("area %d = %f\n",i,temp);
    if(temp<=smallValue){
      smallId = i;
      smallValue = temp;
    }
    if(temp>=largeValue){
      largeId = i;
      largeValue = temp;
    }
  }

  printf("%d %d",smallId+1,largeId+1);

  return 0;
}

2 thoughts on “CodeChef: Find Area of Triangles

  1. Anon

    Hey Daniel! This is a problem from an ongoing contest and you shouldn’t be posting solutions before it gets over. I am sure this will be helpful but not now. Please hide this post and make it visible after a few days when the contest is over. If the admins at codechef get to know about this, they might ban you.

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *