language: C++ 4.7.2 (gcc-4.7.2)
date: 645 days 18 hours ago
link:
visibility: public 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

// Implementation of Monotone Chain Convex Hull algorithm.
#include <algorithm>
#include <vector>
#include <cstdio>
#include<iostream>
using namespace std;
 
typedef double CoordType;
 
struct Point {
        CoordType x, y;
 
        bool operator <(const Point &p) const {
                return x < p.x || (x == p.x && y < p.y);
        }
};
 
// 2D cross product.
// Return a positive value, if OAB makes a counter-clockwise turn,
// negative for clockwise turn, and zero if the points are collinear.
CoordType cross(const Point &O, const Point &A, const Point &B)
{
        return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}
 
// Returns a list of points on the convex hull in counter-clockwise order.
// Note: the last point in the returned list is the same as the first one.
vector<Point> convexHull(vector<Point>& P)
{
        int n = P.size(), k = 0;
        vector<Point> H(2*n);
 
        // Sort points lexicographically
        sort(P.begin(), P.end());
 
        // Build lower hull
        for (int i = 0; i < n; i++) {
                while (k >= 2 && cross(H[k-2], H[k-1], P[i]) <= 0) k--;
                H[k++] = P[i];
        }
 
        // Build upper hull
        for (int i = n-2, t = k+1; i >= 0; i--) {
                while (k >= t && cross(H[k-2], H[k-1], P[i]) <= 0) k--;
                H[k++] = P[i];
        }
 
        H.resize(k-1);
        return H;
}
 
vector<Point> points, result;
 
double area(int a, int b, int c)
{
        double calc = result[a].x*result[b].y - result[a].x*result[c].y + result[b].x*result[c].y 
        - result[b].x*result[a].y + result[c].x*result[a].y - result[c].x*result[b].y;
        return calc/2.0;
}
 
// biggest triangle O(n)
double biggest()
{
        int n = result.size();
        // Assume points have been sorted already, as 0...(n-1)
        int A = 0, B = 1, C = 2;
        int bA= A, bB= B, bC= C; // The "best" triple of points
        double best = area(A, B, C); // Best area
        
        while (1) // loop A
        {
                while (1) // loop B
                {
                        while (area(A, B, C) <= area(A, B, (C+1)%n)) // loop C
                                C = (C+1)%n;
                        if (area(A, B, C) <= area(A, (B+1)%n, C))
                                B = (B+1)%n;
                        else
                                break;
                }
 
                double test = area(A, B, C);
                if (test > best)
                {
                        bA = A; bB = B; bC = C;
                        best = test;
                }
 
                A = (A+1)%n;
                if (A==B) B = (B+1)%n;
                if (B==C) C = (C+1)%n;
                if (A==0) break;
        }
 
        //cout<<result[bA].x <<" "<<result[bA].y <<" "<<result[bB].x<<" "<<result[bB].y<<" "<<result[bC].x <<" "<<result[bC].y<<" best = "<<best <<endl;        
        return best;
}
 
int main()
{
        int n;
        
        while (1)
        {
                scanf("%d", &n);
                if (n == -1)
                        break;
                        
                points.clear();
                
                for (int i = 0; i < n; ++i)
                {
                        Point p;
                        scanf("%lf%lf", &p.x, &p.y);
                        points.push_back(p);
                }
                
                result = convexHull(points);
                //for(int i=0;i<result.size();i++) cout<<result[i].x <<" "<<result[i].y<<endl;
                double res = biggest();
                printf("%.2lf\n", res);
        }
        
        return 0;
}
 
prog.cpp: In function ‘int main()’:
prog.cpp:105: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
prog.cpp:114: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result
  • upload with new input
  • # 3:   show   clone   input   645 days 18 hours ago    Success
  • # 2:   show   clone   input   645 days 18 hours ago    Success
  • # 1:   hide   clone   input   645 days 18 hours ago

    result: Runtime error     time: 0s    memory: 2860 kB     signal: 6 

    terminate called after throwing an instance of 'std::length_error'
  what():  vector::_M_fill_insert