Pagini recente » Cod sursa (job #1354302) | Cod sursa (job #1324381) | Cod sursa (job #3335075) | Cod sursa (job #2457913) | Cod sursa (job #1020408)
#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;
}