fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. struct Point {
  9.     int x, y;
  10. };
  11.  
  12. int calculateArea(const Point& p1, const Point& p2, const Point& p3) {
  13.     return abs((p1.x * (p2.y - p3.y) + p2.x * (p3.y - p1.y) + p3.x * (p1.y - p2.y)) / 2);
  14. }
  15.  
  16. bool comparePoints(const Point& p1, const Point& p2) {
  17.     return (p1.x < p2.x) || (p1.x == p2.x && p1.y < p2.y);
  18. }
  19.  
  20. int findMaxArea(vector<Point>& points, int n) {
  21.     int maxArea = 0;
  22.  
  23.     sort(points.begin(), points.end(), comparePoints);
  24.  
  25.     for (int i = 0; i < n - 2; ++i) {
  26.         for (int j = i + 1; j < n - 1; ++j) {
  27.             for (int k = j + 1; k < n; ++k) {
  28.                 int area = calculateArea(points[i], points[j], points[k]);
  29.                 maxArea = max(maxArea, area);
  30.             }
  31.         }
  32.     }
  33.  
  34.     return maxArea;
  35. }
  36.  
  37. int main() {
  38.    // freopen("POLY4MAX.INP", "r", stdin);
  39.    // freopen("POLY4MAX.OUT", "w", stdout);
  40.  
  41.     int n;
  42.     cin >> n;
  43.  
  44.     vector<Point> points(n);
  45.     for (int i = 0; i < n; ++i) {
  46.         cin >> points[i].x >> points[i].y;
  47.     }
  48.  
  49.     int maxArea = findMaxArea(points, n);
  50.  
  51.     cout << maxArea << ".0";  // Write the result with 1 decimal place
  52.  
  53.     return 0;
  54. }
  55.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
6
2 1
2 3
5 7
8 3
8 1
5 0
stdout
copy 
18.0
https://ideone.com/IQ9IS0
language:
C++14 (clang 8.0)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!