Advertisement
Guest User

Untitled

a guest
Apr 7th, 2020
249
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.89 KB | None | 0 0
  1. #include <iostream>
  2. #include <float.h>
  3. #include <stdlib.h>
  4. #include <math.h>
  5. using namespace std;
  6.  
  7. struct Point {
  8.     int x, y;
  9. };
  10.  
  11. struct Triangle {
  12.     Point a, b, c;
  13. };
  14.  
  15. Triangle FINAL_TRIANGLE;
  16. float SMALLEST_PERIMETER = FLT_MAX;
  17.  
  18. void printPoint(Point p) {
  19.     printf("%d %d", p.x, p.y);
  20. }
  21.  
  22. void printTriangle(Triangle t) {
  23.     printPoint(t.a);
  24.     printf("\n");
  25.     printPoint(t.b);
  26.     printf("\n");
  27.     printPoint(t.c);
  28. }
  29.  
  30. float min(float x, float y) {
  31.     return (x < y)? x : y;
  32. }
  33.  
  34. int compareX(const void* a, const void* b) {
  35.     Point *p1 = (Point *)a, *p2 = (Point *)b;
  36.     return (p1->x - p2->x);
  37. }
  38.  
  39. int compareY(const void* a, const void* b) {
  40.     Point *p1 = (Point *)a, *p2 = (Point *)b;
  41.     return (p1->y - p2->y);
  42. }
  43.  
  44. float distance(Point p1, Point p2) {
  45.     return sqrt(((long long)p1.x - (long long)p2.x) * ((long long)p1.x - (long long)p2.x) +
  46.                (((long long)p1.y - (long long)p2.y) * ((long long)p1.y - (long long)p2.y)));
  47. }
  48.  
  49. float perimeter(Point p1, Point p2, Point p3) {
  50.     return distance(p1, p2) + distance(p1, p3) + distance(p2, p3);
  51. }
  52.  
  53. float smallestPerimeter(Point points[], int n) {
  54.     float min = FLT_MAX;
  55.     for (int i = 0; i < n - 2; ++i)
  56.         for (int j = i + 1; j < n; ++j)
  57.             for (int k = j + 1; k < n; ++k) {
  58.                 float perimeterToCheck = perimeter(points[i], points[j], points[k]);
  59.                 if (perimeterToCheck < min)
  60.                     min = perimeterToCheck;
  61.                 if (perimeterToCheck < SMALLEST_PERIMETER) {
  62.                     SMALLEST_PERIMETER = perimeterToCheck;
  63.                     FINAL_TRIANGLE = {points[i], points[j], points[k]};
  64.                 }
  65.             }
  66.     return min;
  67. }
  68.  
  69. float smallestNearTheLine(Point pointsNearLine[], int size, float p) {
  70.     float min = p;
  71.     qsort(pointsNearLine, size, sizeof(Point), compareY);
  72.     for (int i = 0; i < size; ++i)
  73.         for (int j = i + 1; j < size && abs(pointsNearLine[i].y - pointsNearLine[j].y) < p; ++j)
  74.             for(int k = j + 1; k < size && abs(pointsNearLine[i].y - pointsNearLine[k].y) < p; ++k) {
  75.                 float perimeterToCheck = perimeter(pointsNearLine[i], pointsNearLine[j], pointsNearLine[k]);
  76.                 if (perimeterToCheck < min) {
  77.                     min = perimeterToCheck;
  78.                 }
  79.                 if (perimeterToCheck < SMALLEST_PERIMETER) {
  80.                     SMALLEST_PERIMETER = perimeterToCheck;
  81.                     FINAL_TRIANGLE = {pointsNearLine[i], pointsNearLine[j], pointsNearLine[k]};
  82.                 }
  83.             }
  84.  
  85.     return min;
  86. }
  87.  
  88. float divideTheProblem(Point xSorted[], int n)
  89. {
  90.     if (n <= 9)
  91.         return smallestPerimeter(xSorted, n);
  92.  
  93.     int mid = n/2;
  94.     int midPointX = xSorted[mid].x;
  95.  
  96.     float smallestPerimeterOnTheLeft = divideTheProblem(xSorted, mid);
  97.     float smallestPerimeterOnTheRight = divideTheProblem(xSorted + mid, n - mid);
  98.    
  99.     float perimeter = min(smallestPerimeterOnTheRight, smallestPerimeterOnTheLeft);
  100.  
  101.     Point pointsNearLine[n];
  102.     int count = 0;
  103.     for (int i = 0; i < n; i++)
  104.         if (abs(xSorted[i].x - midPointX) < (perimeter / 2)) {
  105.             pointsNearLine[count] = xSorted[i];
  106.             count++;
  107.         }
  108.    
  109.     return min(perimeter, smallestNearTheLine(pointsNearLine, count, perimeter));
  110. }
  111.  
  112. void smallestTriangle(Point points[], int n) {
  113.    
  114.     qsort(points, n, sizeof(Point), compareX);
  115.  
  116.     float smallestTrianglePerimeter = divideTheProblem(points, n);
  117. }
  118.  
  119. int main() {
  120.     std::ios_base::sync_with_stdio(false);
  121.     std::cin.tie(NULL);
  122.    
  123.     int n;
  124.     cin >> n;
  125.    
  126.     Point points[n];
  127.    
  128.     for(int i = 0; i < n; i++) {
  129.         int x, y;
  130.         cin >> x;
  131.         cin >> y;
  132.        
  133.         Point p;
  134.         p = {x, y};
  135.         points[i] = p;
  136.     }
  137.    
  138.     smallestTriangle(points, n);
  139.     printTriangle(FINAL_TRIANGLE);
  140.     cout << endl;
  141. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement