Pagini recente » Cod sursa (job #2281013) | Cod sursa (job #2473881) | Cod sursa (job #259261) | Cod sursa (job #2909853) | Cod sursa (job #2207274)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <math.h>
#include <iomanip>
#define dMAX 100
#define PI 3.141592
using namespace std;
int n;
struct Point{
float x, y;
} arr[dMAX + 2];
Point myStack[dMAX + 2];
int idx;
ifstream fin("infasuratoareconvexa.in");
ofstream fout("infasuratoareconvexa.out");
float Angle(Point q) {
float t = atan2(q.y - arr[1].y, q.x - arr[1].x);
if (t < 0) return 2 * PI + t;
return t;
}
bool Compare(Point p, Point q) {
if (p.y == q.y) return p.x < q.x;
return p.y < q.y;
}
bool CompareA(Point p, Point q) {
return Angle(p) < Angle(q);
}
int Orientation(Point p, Point q, Point r) {
int t = ((r.x - q.x) * (q.y - p.y) - (q.x - p.x) * (r.y - q.y));
if (t < 0) return -1;
if (t == 0) return 0;
if (t > 0) return 1;
}
int main()
{
int i, j;
fin >> n;
for (i = 1; i <= n; i++) {
fin >> arr[i].x >> arr[i].y;
}
if (n < 3) {
fout << 0;
return 0;
}
sort(arr + 1, arr + 1 + n, Compare);
sort(arr + 1, arr + 1 + n, CompareA);
myStack[++idx] = arr[1];
myStack[++idx] = arr[2];
myStack[++idx] = arr[3];
for (i = 4; i <= n; i++) {
while (Orientation(myStack[idx - 1], myStack[idx], arr[i]) != -1 && idx >= 2) {
idx--;
}
myStack[++idx] = arr[i];
}
if (idx < 3) {
fout << 0;
return 0;
}
fout << idx << '\n';
for (i = 1; i <= idx; i++) {
fout << setprecision(6) << fixed << myStack[i].x << ' ' << myStack[i].y << '\n';
}
return 0;
}