Ciel and Map

Problem Link : http://www.codechef.com/problems/CIELMAP/

Idea : Given some point N . You have to find out the larger side of a quadrilateral that can be formed by 4 out of N point . The boundary of the quadrilateral may not be crossed by itself .

If N>4 , our answer is the distance between the farthest couple of points .
It can be determined using loop .

If N=4 , then we have to face the calculation for possible all quadrilateral .
For possible all permutation , we have to calculate two thing -

1. Whether the quadrilateral cross its own boundary or not .
2. If yes , skip this quadrilateral .
   Else , take the maximum side for count .

We can easily find out 1st requirment using the concept of vector cross product .

If points are A,B,C and D.

If the sign of AB*AC and AC*AD are same , that means all points are consecutively clockwise or anti-clockwise and a valid quadrilateral is possible . Then calculate AB , BC , CD , AD and take the maximum value of side for counting .

My Solution