Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <float.h>
- #include <stdlib.h>
- #include <math.h>
- using namespace std;
- struct Point {
- int x, y;
- };
- struct Triangle {
- Point a, b, c;
- };
- Triangle FINAL_TRIANGLE;
- float SMALLEST_PERIMETER = FLT_MAX;
- void printPoint(Point p) {
- printf("%d %d", p.x, p.y);
- }
- void printTriangle(Triangle t) {
- printPoint(t.a);
- printf("\n");
- printPoint(t.b);
- printf("\n");
- printPoint(t.c);
- }
- float min(float x, float y) {
- return (x < y)? x : y;
- }
- int compareX(const void* a, const void* b) {
- Point *p1 = (Point *)a, *p2 = (Point *)b;
- return (p1->x - p2->x);
- }
- int compareY(const void* a, const void* b) {
- Point *p1 = (Point *)a, *p2 = (Point *)b;
- return (p1->y - p2->y);
- }
- float distance(Point p1, Point p2) {
- return sqrt(((long long)p1.x - (long long)p2.x) * ((long long)p1.x - (long long)p2.x) +
- (((long long)p1.y - (long long)p2.y) * ((long long)p1.y - (long long)p2.y)));
- }
- float perimeter(Point p1, Point p2, Point p3) {
- return distance(p1, p2) + distance(p1, p3) + distance(p2, p3);
- }
- float smallestPerimeter(Point points[], int n) {
- float min = FLT_MAX;
- for (int i = 0; i < n - 2; ++i)
- for (int j = i + 1; j < n; ++j)
- for (int k = j + 1; k < n; ++k) {
- float perimeterToCheck = perimeter(points[i], points[j], points[k]);
- if (perimeterToCheck < min)
- min = perimeterToCheck;
- if (perimeterToCheck < SMALLEST_PERIMETER) {
- SMALLEST_PERIMETER = perimeterToCheck;
- FINAL_TRIANGLE = {points[i], points[j], points[k]};
- }
- }
- return min;
- }
- float smallestNearTheLine(Point pointsNearLine[], int size, float p) {
- float min = p;
- qsort(pointsNearLine, size, sizeof(Point), compareY);
- for (int i = 0; i < size; ++i)
- for (int j = i + 1; j < size && abs(pointsNearLine[i].y - pointsNearLine[j].y) < p; ++j)
- for(int k = j + 1; k < size && abs(pointsNearLine[i].y - pointsNearLine[k].y) < p; ++k) {
- float perimeterToCheck = perimeter(pointsNearLine[i], pointsNearLine[j], pointsNearLine[k]);
- if (perimeterToCheck < min) {
- min = perimeterToCheck;
- }
- if (perimeterToCheck < SMALLEST_PERIMETER) {
- SMALLEST_PERIMETER = perimeterToCheck;
- FINAL_TRIANGLE = {pointsNearLine[i], pointsNearLine[j], pointsNearLine[k]};
- }
- }
- return min;
- }
- float divideTheProblem(Point xSorted[], int n)
- {
- if (n <= 9)
- return smallestPerimeter(xSorted, n);
- int mid = n/2;
- int midPointX = xSorted[mid].x;
- float smallestPerimeterOnTheLeft = divideTheProblem(xSorted, mid);
- float smallestPerimeterOnTheRight = divideTheProblem(xSorted + mid, n - mid);
- float perimeter = min(smallestPerimeterOnTheRight, smallestPerimeterOnTheLeft);
- Point pointsNearLine[n];
- int count = 0;
- for (int i = 0; i < n; i++)
- if (abs(xSorted[i].x - midPointX) < (perimeter / 2)) {
- pointsNearLine[count] = xSorted[i];
- count++;
- }
- return min(perimeter, smallestNearTheLine(pointsNearLine, count, perimeter));
- }
- void smallestTriangle(Point points[], int n) {
- qsort(points, n, sizeof(Point), compareX);
- float smallestTrianglePerimeter = divideTheProblem(points, n);
- }
- int main() {
- std::ios_base::sync_with_stdio(false);
- std::cin.tie(NULL);
- int n;
- cin >> n;
- Point points[n];
- for(int i = 0; i < n; i++) {
- int x, y;
- cin >> x;
- cin >> y;
- Point p;
- p = {x, y};
- points[i] = p;
- }
- smallestTriangle(points, n);
- printTriangle(FINAL_TRIANGLE);
- cout << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement