Pagini recente » Cod sursa (job #1699278) | Cod sursa (job #837166) | Cod sursa (job #974347) | Cod sursa (job #1186806) | Cod sursa (job #2297172)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#define pii pair <double, double>
#define x first
#define y second
#include <iomanip>
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
vector <pii> v;
int st[120010], st1[120010];
int n, top, top1;
double a, b;
double det (pii a, pii b, pii c){
int 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;
v.push_back({0, 0});
for (int i=1; i<=n; i++){
fin >> a >> b;
v.push_back({a, b});
}
sort (v.begin(), v.end());
for (int i=1; i<=n; i++){
cout << v[i].x << ' ' << v[i].y << '\n';
}
st[++top] = 1;
for (int i=2; i<=n; i++){
if (top == 1)
st[++top] = i;
else{
while (top >=2 && det (v[st[top-1] ], v[ st[top] ], v[i] ) > 0)
top--;
st[++top] = i;
}
}
st1[++top1] = 1;
for (int i=2; i<=n; i++){
if (top1 == 1)
st1[++top1] = i;
else{
while (top1 >=2 && det (v[st1[top1-1] ], v[ st1[top1] ], v[i] ) < 0)
top1--;
st1[++top1] = i;
}
}
fout << top1 + top - 2 << '\n';
for (int i=1; i<=top1; i++)
fout << setprecision(6) << v[st1[i]].x << ' ' << v[st1[i]].y << '\n';
for(int i=top-1; i>1; i--)
fout << setprecision(6) << v[st[i]].x << ' ' << v[st[i]].y << '\n';
return 0;
}