Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <stdlib.h>
- #include <stdio.h>
- #include <algorithm>
- #include <math.h>
- using namespace std;
- static const int N = 1000;
- struct vektor
- {
- int x, y;
- };
- long long vp(vektor a, vektor b)
- {
- long long p1 = a.x;
- long long p2 = b.x;
- p1 *= b.y;
- p2 *= a.y;
- return p1 - p2;
- }
- int n;
- vektor niz[N];
- int next[N];
- int prev[N];
- vektor convex[N];
- bool lower(int i, int j)
- {
- if(niz[i].y < niz[j].y)
- return 1;
- if(niz[i].y == niz[j].y)
- if(niz[i].x < niz[j].x)
- return 1;
- return 0;
- }
- bool compare(vektor a, vektor b)
- {
- vektor v1, v2;
- v1.x = a.x - niz[n - 1].x;
- v2.x = b.x - niz[n - 1].x;
- v1.y = a.y - niz[n - 1].y;
- v2.y = b.y - niz[n - 1].y;
- long long sol = vp(v1, v2);
- return (sol > 0);
- }
- bool ok(int cur)
- {
- vektor v1, v2;
- v1.x = convex[cur].x - convex[cur - 1].x;
- v1.y = convex[cur].y - convex[cur - 1].y;
- v2.x = convex[cur - 1].x - convex[cur - 2].x;
- v2.y = convex[cur - 1].y - convex[cur - 2].y;
- return (vp(v1, v2) < 0);
- }
- double duz(vektor v)
- {
- double res1 = v.x;
- double res2 = v.y;
- res1 *= res1;
- res2 *= res2;
- res1 += res2;
- return sqrt(res1);
- }
- double dist(int a, int b, int c)
- {
- vektor u = convex[c];
- vektor v = convex[b];
- u.x -= v.x;
- u.y -= v.y;
- vektor k = convex[a];
- k.x -= v.x;
- k.y -= v.y;
- double sin = ((double) k.x * u.y) - ((double) k.y * u.x);
- sin /= duz(u);
- if(sin < 0)
- sin *= -1;
- return sin;
- }
- double povrs(int a, int c, int b, int d)
- {
- // printf("%i %i %i %i\n", a, b, c, d);
- vektor v = convex[a];
- vektor u = convex[c];
- u.x -= v.x;
- u.y -= v.y;
- double dz = duz(u);
- double res = 0;
- res += dist(b, a, c);
- res += dist(d, a, c);
- res /= 2;
- res *= dz;
- // printf("%lf\n\n", res);
- return res;
- }
- int main()
- {
- freopen("input.txt", "r", stdin);
- scanf("%i", &n);
- while(n != -1)
- {
- for(int i = 0; i < n; i++)
- {
- scanf("%i", &niz[i].x);
- scanf("%i", &niz[i].y);
- }
- int extreme = 0;
- for(int i = 1; i < n; i++)
- if(lower(i, extreme))
- extreme = i;
- swap(niz[n - 1], niz[extreme]);
- sort(niz, niz + n - 1, compare);
- /*
- printf("\n %i %i\n", niz[n - 1].x, niz[n - 1].y);
- for(int i = 0; i < n - 1; i++)
- printf("%i %i\n", niz[i].x, niz[i].y);
- scanf("%i", &n);
- */
- convex[0] = niz[n - 1];
- convex[1] = niz[0];
- int cur = 2;
- for(int i = 1; i < n - 1; i++)
- {
- convex[cur] = niz[i];
- while(cur > 2 && !ok(cur))
- {
- swap(convex[cur], convex[cur - 1]);
- cur--;
- }
- cur++;
- }
- /*
- for(int i = 0; i < cur; i++)
- printf("%i %i\n", convex[i].x, convex[i].y);
- printf("\n\n");
- */
- double best = 0;
- if(cur > 3)
- {
- for(int i = 0; i < cur; i++)
- {
- next[i] = (i + 1) % cur;
- prev[i] = (i - 1) % cur;
- }
- for(int i = 0; i < cur; i++)
- {
- int n = cur;
- int d = next[i];
- int m = next[d];
- int j = m;
- for(int g = next[m]; g != i; g = next[g])
- if(dist(g, i, j)> dist(m, i, j))
- m = g;
- int g = m;
- //printf("%i %i %i %i\n", i, (i + 2) % n, d, g);
- if(povrs(i, j, d, g) > best)
- best = povrs(i, j, d, g);
- for(j = next[j]; j != prev[i]; j = next[j])
- {
- while(dist(next[g], i, j) > dist(g, i, j) && g != i)
- g = next[g];
- while(dist(next[d], i, j) > dist(d, i, j) && d != j)
- d = next[g];
- //printf("%i %i %i %i\n", i, j, d, g);
- if(povrs(i, j, d, g) > best)
- best = povrs(i, j, d, g);
- }
- }
- }
- if(cur == 3)
- {
- best = -1;
- for(int i = 0; i < n; i++)
- {
- int k = 0;
- for(int j = 0; j < cur; j++)
- if(convex[j].x == niz[i].x && convex[j].y == niz[i].y)
- k = 1;
- if(!k)
- {
- //printf("%i %i\n", niz[i].x, niz[i].y);
- convex[3] = niz[i];
- for(int j = 0; j < 3; j++)
- {
- vektor v = convex[j];
- vektor u = convex[(j + 1) % 3];
- u.x -= v.x;
- u.y -= v.y;
- double pom = duz(u);
- pom /= 2;
- pom *= dist(3, j, (j + 1) % 3);
- if(pom < best || best == -1)
- best = pom;
- }
- }
- }
- best += povrs(0, 1, 0, 2);
- }
- printf("%lf\n", best);
- scanf("%i", &n);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement