Pagini recente » Cod sursa (job #1238724) | Cod sursa (job #1392468) | Cod sursa (job #1392434) | Cod sursa (job #2750395) | Cod sursa (job #1020391)
#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;
}