# My Weblog

## 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