## 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); } }

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 |