infoarena

s1[1] = c[1]; //s1[i] = suma maxima editandu-se primii i pari, c[i] = aria pe care o castiga prin mutarea parului i
	sm1[1] = 1; // sm1[i] = retine 1 daca s-a mutat parul i, 0 in caz contrar
	if(c[1] > c[2]) s1[2] = c[1], sm1[2] = 0; else s1[2] = c[2], sm1[2] = 1;
	for(int i=3;i<n;i++)
	{
		if(s1[i-2] + c[i] > s1[i-1]) s1[i] = s1[i-2] + c[i], sm1[i] = 1; else s1[i] = s1[i-1], sm1[i] = 0;
	}
	
	s2[2] = c[2];
	sm2[2] = 1;
	if(c[2] > c[3]) s2[3] = c[2], sm2[3] = 0; else s2[3] = c[3], sm2[3] = 1;
	for(int i=4;i<=n;i++)
	{
		if(s2[i-2] + c[i] > s2[i-1]) s2[i] = s2[i-2] + c[i], sm2[i] = 1; else s2[i] = s2[i-1], sm2[i] = 0;
	}
	
	smax1 = s1[n-1]; smax2 = s2[n];
	if(!(sm1[1]) && !(sm1[n-1])) smax1 += c[n];
	if(!(sm2[2]) && !(sm2[n])) smax2 += c[1];

           float smax = max(smax1, smax2);

inline bool cmp(int a, int b)
{
	return (float)(x[a] - x[PI])*(y[b] - y[PI]) < (float)(x[b] - x[PI])*(y[a] - y[PI]);
}

for(int i=1;i<=n;i++)
	{
		if(i == PI) continue;
		IN[++IN[0]] = i;
	}
	
	sort(IN + 1, IN + IN[0] + 1, cmp);
	IN[++IN[0]] = PI;
	
	for(int i=1;i<=n;i++)
	{
		int dr = i+1, st = i-1;
		if(dr > n) dr = 1;
		if(st < 1) st = n;
		float D = (float)dist((float)x[IN[st]], (float)y[IN[st]], (float)x[IN[dr]], (float)y[IN[dr]]);
		c[i] = (float)(D * d[IN[i]]) / 2;
	}

int cmp (punct a,punct b)
{
    return atan2 (a.y-gy,a.x-gx)<atan2 (b.y-gy,b.x-gx);
}

8
0 0 2
2 0 3
0 1 2
0 -1 1
1 1 2
2 -1 4
2 1 3

int Produs(Puncte P1, Puncte P2, Puncte P3) {
    return P2.x*P3.y - P2.x*P1.y - P1.x*P3.y + P1.x*P1.y - 
           P3.x*P2.y + P3.x*P1.y + P1.x*P2.y - P1.x*P1.y;
}

int cmp(Puncte a, Puncte b) {
    if((a.x-P[1].x)*(b.y-P[1].y)!=(b.x-P[1].x)*(a.y-P[1].y)) {
         return (a.x-P[1].x)*(b.y-P[1].y) > (b.x-P[1].x)*(a.y-P[1].y);
    }
    else if(P[1].y==a.y && P[1].y==b.y) {
         return (a.x-P[1].x)*(a.x-P[1].x) + (a.y-P[1].y)*(a.y-P[1].y) <
                (b.x-P[1].x)*(b.x-P[1].x) + (b.y-P[1].y)*(b.y-P[1].y);
    }
    else if(!Produs(a, b, P[1])) {
          return a.x<b.x;
    }
}

19
-6 19 1
18 -17 9
-16 -18 8
-19 -3 10
19 -8 10
17 18 3
19 -12 2
-8 -19 3
-19 16 7
-18 -16 7
19 -6 9
-17 18 5
19 15 2
-19 -2 3
13 19 4
7 -19 10
0 19 6
-19 -15 5
-4 -19 1

467.9360045