Pagini recente » Cod sursa (job #1957633) | Cod sursa (job #1698804) | Cod sursa (job #992565) | Cod sursa (job #741527) | Cod sursa (job #2207277)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <math.h>
#include <iomanip>
#define dMAX 120000
#define PI 3.141592
using namespace std;
int n, c;
struct Point{
float x, y;
} arr[dMAX + 2];
Point myStack[dMAX + 2];
int idx;
bool marked[dMAX + 2];
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.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);
for (i = 1; i <= n; i++) {
if (Angle(arr[i]) == Angle(arr[i + 1])) {
marked[i] = true;
}
}
/*myStack[++idx] = arr[1];
myStack[++idx] = arr[2];
myStack[++idx] = arr[3];*/
for (i = 1; i <= n; i++) {
if (!marked[i]) {
myStack[++idx] = arr[i];
c++;
}
if (c == 3) break;
}
for (i = 4; i <= n; i++) {
if (marked[i]) continue;
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;
}