Pagini recente » Cod sursa (job #471295) | Cod sursa (job #2762056) | Cod sursa (job #1573725) | Cod sursa (job #2747725) | Cod sursa (job #2297202)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
struct punct{double x,y; } v[120010];
int st[120010];
int n, top;
int comp (punct a, punct b)
{
if (a.x < b.x)
{
if (a.y < b.y)
return 1;
return 0;
}
return 0;
}
double det (punct a, punct b, punct c){
double ans = a.x * b.y + b.x * c.y + c.x * a.y - c.x * b.y - a.x * c.y - b.x * a.y;
return ans;
}
int main()
{
fin >> n;
for (int i=1; i<=n; i++){
fin >> v[i].x >> v[i].y;
}
sort (v+1, v + n + 1, comp);
st[1] = 1;
st[2] = 2;
top = 2;
for (int i=3; i<=n; i++){
while (top >=2 && det (v[st[top-1] ], v[ st[top] ], v[i] ) > 0)
top--;
st[++top] = i;
}
for (int i=n-1; i>=1; i--){
while (top >=2 && det (v[st[top-1] ], v[ st[top] ], v[i] ) > 0)
top--;
st[++top] = i;
}
fout << top - 1 << '\n';
for (int i=top-1; i>=1; i--)
fout << setprecision(6) << v[st[i]].x << ' ' << v[st[i]].y << '\n';
fin.close();
fout.close();
return 0;
}