Pagini recente » Cod sursa (job #1519297) | Cod sursa (job #2293443) | Cod sursa (job #1253010) | Cod sursa (job #1329388) | Cod sursa (job #2451990)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
#define ARRAY_MAX 120001
struct Point {
double x, y;
};
int N, top;
Point arr[ARRAY_MAX];
Point stackData[ARRAY_MAX];
void Read() {
fin >> N;
for (int i = 1; i <= N; i++)
fin >> arr[i].x >> arr[i].y;
}
double angularCoefficient(Point& A, Point& B, Point& C) {
return (C.y - A.y) * (B.x - A.x) - (B.y - A.y) * (C.x - A.x);
}
int compareValue(Point& firstVal, Point& secondVal) {
return angularCoefficient(arr[1], firstVal, secondVal) < 0;
}
void sortPoints() {
int currentPosition = 1;
for (int i = 2; i <= N; i++)
if (arr[i].x < arr[currentPosition].x)
currentPosition = i;
swap(arr[1], arr[currentPosition]);
sort(arr + 2, arr + N + 1, compareValue);
}
void GrahamScan() {
sortPoints();
stackData[1] = arr[1];
stackData[2] = arr[2];
top = 2;
for (int i = 3; i <= N; i++) {
while (top >= 2 && angularCoefficient(stackData[top - 1], stackData[top], arr[i]) > 0)
top--;
stackData[++top] = arr[i];
}
}
void Write() {
fout << fixed << top << "\n";
for (int i = top; i >= 1; i--)
fout << setprecision(6) <<stackData[i].x << " " << stackData[i].y << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
fin.tie(NULL);
fout.tie(NULL);
Read();
GrahamScan();
Write();
}