Pagini recente » Cod sursa (job #3232890) | Cod sursa (job #1845501) | Cod sursa (job #2881780) | Cod sursa (job #878360) | Cod sursa (job #3030178)
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<double, double> pt;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
const int N = 12e4 + 5;
int n, rez[N];
pt v[N];
void init(), read();
inline double det(pt, pt, pt);
inline bool sortTrig(pt, pt);
int main()
{
init();
rez[1] = 1; int k = 2;
for (int i = 2; i < n; i++){
while (det(v[rez[k - 2]], v[rez[k - 1]], v[i]) <= 0 && k > 2) k--;
rez[k] = i; k++;
}
g << k << '\n' << fixed << setprecision(12);
for (int i = 0; i <k; i++) g << v[rez[i]].x << ' ' << v[rez[i]].y << '\n';
return 0;
}
void read() {
f >> n;
for (int i = 0; i < n; i++)
f >> v[i].x >> v[i].y;
}
void init(){
read();
int lo = 0;
for (int i = 1; i < n; i++)
if (v[i] < v[lo]) lo = i;
swap(v[0], v[lo]);
sort(v + 1, v + n, sortTrig);
}
inline double det(pt a, pt b, pt c){
return a.x*b.y + b.x*c.y + c.x*a.y - b.x*a.y - c.x*b.y - a.x*c.y;
}
inline bool sortTrig(pt a, pt b){
int Det = det(v[0], a, b);
return (Det > 0);
}