My Weblog

Blog about programming and math

SPOJ problem INTEGMAX

This problem ask to maximize the area of polygon.The area of polygon having n points 0.5 [y_0(x_n-1-x_1)+y_1(x_0-x_2)+ y_2(x_2-x_3)+………….+y_n-1(x_n-2-x_0)].There are K points given but we have two more points on the X axis (x_0,0) and (x_K-1,0) so we have to add these two points into x_array and y_array but these two points are fixed so we can permute only K points of y_array not the whole K+2 points[we have to exclude y_0 and y_K+1].Calculate all the difference of x_array in the given area formula but remember we have y_0 and y_n-1 [first and last point y coordinate which are fixed ] are 0 so we don’t need (x_n-1-x_1) and (x_n-2-x_0) so remove it from x_array. Now sort the difference in both increasing and decreasing order and take the maximum of both.

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
typedef pair<int,int> PI;
vector<long long> vx,vy,ret;
int main()
       {
       
          long long t,k;
	  double sum_1,sum_2,sum;
	  int n;
          while(scanf("%lld",&t) && t!=-1)
          {
             vx.clear(),vy.clear(),ret.clear();sum_1=sum_2=sum=0;
             for(int i=0;i<t;i++) scanf("%lld",&k),vx.push_back(k);
             for(int i=0;i<t;i++) scanf("%lld",&k),vy.push_back(k);
             vx.push_back(vx[0]);
             vx.push_back(vx[t-1]);
             sort(vx.begin(),vx.end());
             sort(vy.begin(),vy.end());
             n=t+2;
             for(int i=0;i<n;i++) ret.push_back(vx[(n+i-1)%n]-vx[(i+1)%n]);
	     ret.erase(ret.begin(),ret.begin()+1);
	     ret.erase(ret.end()-1,ret.end());
             sort(ret.begin(),ret.end());  
             for(int i=0;i<t;i++) sum_1+=ret[i]*vy[i];
	     sort(ret.rbegin(),ret.rend());
	     for(int i=0;i<t;i++) sum_2+=ret[i]*vy[i];
	     sum=max(fabs(sum_1),fabs(sum_2))*0.5;
             printf("%.1lf\n",sum);
          }   
       }
Advertisements

December 11, 2010 - Posted by | Programming

1 Comment »

  1. nice one 🙂 but i guess we can do this without using another new vector ret which is using lot of memory unnecessarily

    Comment by gratitude | March 11, 2015 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: