Cod sursa(job #1020392)

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

#define MAX_COORDINATE 1000000001.0f
#define PLUS_INFINITY 999999999.0f

using namespace std;

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

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

float 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){
    float sw = tangents[index1];
    POINT swapPoint = points[index1];

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

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


int compare(float value1, float 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;

    float 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 point3 =st.top();
    st.pop();

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

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

    float crossProduct =(point2.x - point1.x)*(point3.y - point1.y) - (point3.x - point1.x)*(point2.y-point1.y);

    if (crossProduct > 0){
        //left turn
        st.push(point1);
        st.push(point2);
        st.push(point3);

    } else {
        //right turn or collinear
        st.push(point1);
        st.push(point3);
    }
}

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]){
            float 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);

            float 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("%f %f\n", p.x, p.y);
    }

}

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

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

    float minX = MAX_COORDINATE;

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

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

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

    float 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(points[0]);
    pointsStack.push(points[1]);
    pointsStack.push(points[2]);

    checkForRightTurn(pointsStack);

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

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

    printValues(pointsStack);

    return 0;
}