• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

a guest Apr 7th, 2020 200 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.
Top