Cod sursa(job #1020408)

Utilizator sziliMandici Szilard szili Data 2 noiembrie 2013 00:39:29
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 4.48 kb
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <stack>

#define MAX_COORDINATE 1000000001.0
#define PLUS_INFINITY 999999999.0

using namespace std;

typedef struct point{
    double x;
    double y;
} POINT;

POINT points[120001];
POINT pointsReduced[120001];

double tangents[120001];
int n, newN;

void calculateTangents(int startingPointIndex){
    POINT startingPoint = points[startingPointIndex];

    points[startingPointIndex] = points[0];
    points[0] = startingPoint;

    for (int i=1; i<n; i++){

        if (points[i].x == startingPoint.x){
            tangents[i] = PLUS_INFINITY;
        } else {
            tangents[i] = (points[i].y - startingPoint.y) / (points[i].x - startingPoint.x);
        }
    }
}

void swapPoints(int index1, int index2){
    double sw = tangents[index1];
    POINT swapPoint = points[index1];

    tangents[index1] = tangents[index2];
    points[index1] = points[index2];

    tangents[index2] = sw;
    points[index2] = swapPoint;
}


int compare(double value1, double pivotValue, int valueIndex, int pivotIndex){

    if (value1 < pivotValue || (value1 == pivotValue && valueIndex < pivotIndex)){
        return 1;
    }

    return 0;
}


int partitionArray(int left, int right){
    int middleIndex = (left + right) /2;

    double pivotValue = tangents[middleIndex];
    swapPoints(middleIndex, right);

    int storeIndex = left;
    for (int i=left; i<right; i++){
        if (compare(tangents[i], pivotValue, i, middleIndex)){
            swapPoints(i, storeIndex);
            storeIndex++;
        }
    }

    swapPoints(storeIndex, right);

    return storeIndex;
}

void sortBasedOnTangents(int left, int right){
    if (left < right){
        int middle = partitionArray(left, right);
        sortBasedOnTangents(left, middle-1);
        sortBasedOnTangents(middle+1, right);
    }
}

void checkForRightTurn(stack<POINT> &st, POINT newPoint){

    POINT point2 =st.top();
    st.pop();


    double crossProduct =(point2.x - st.top().x)*(newPoint.y - st.top().y) - (newPoint.x - st.top().x)*(point2.y-st.top().y);

    while (crossProduct <= 0){
        point2 =st.top();
        st.pop();

        crossProduct = (point2.x - st.top().x)*(newPoint.y - st.top().y) - (newPoint.x - st.top().x)*(point2.y-st.top().y);
    }

    st.push(point2);
}

void removeDuplicateTangents(){

    pointsReduced[0] = points[0];
    pointsReduced[1] = points[1];
    newN = 2;

    for (int i=2; i<n; i++){
        if (tangents[i] == tangents[i-1]){
            double distance2Squared = (points[0].x - points[i].x)*(points[0].x - points[i].x)
            + (points[0].y - points[i].y)*(points[0].y - points[i].y);

            double distance1Squared = (points[0].x - points[newN-1].x)*(points[0].x - points[newN-1].x)
            + (points[0].y - points[newN-1].y)*(points[0].y - points[newN-1].y);


            if (distance2Squared > distance1Squared){
                pointsReduced[newN-1] = points[i];
            }
        } else {
            pointsReduced[newN++] = points[i];
        }
    }

}

void printValues(stack<POINT> &st){

    if (st.size() > 0){

        POINT p = st.top();
        st.pop();

        printValues(st);

        printf("%lf %lf\n", p.x, p.y);
    }

}

int main()
{
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);

    scanf("%d", &n);
    double a,b;

    double minX = MAX_COORDINATE;

    for (int i=0; i<n; i++){
        POINT p;
        scanf("%lf %lf", &a, &b);

        if (a < minX){
            minX = a;
        }

        p.x = a;
        p.y = b;
        points[i] = p;
    }

    double minY = MAX_COORDINATE;
    int minIndex = -1;
    for (int i=0; i<n; i++){
        if (points[i].x == minX && points[i].y < minY){
            minIndex = i;
            minY = points[i].y;
        }
    }

    calculateTangents(minIndex);
    sortBasedOnTangents(1, n-1);

    removeDuplicateTangents();

    stack<POINT> pointsStack;

    pointsStack.push(pointsReduced[0]);
    pointsStack.push(pointsReduced[1]);

    checkForRightTurn(pointsStack, pointsReduced[2]);
    pointsStack.push(pointsReduced[2]);

    for (int i=3; i<newN; i++){
        checkForRightTurn(pointsStack, pointsReduced[i]);
        pointsStack.push(pointsReduced[i]);
    }

    printf("%d\n", pointsStack.size());

    printValues(pointsStack);

    return 0;
}