Pagini recente » Cod sursa (job #1017038) | Cod sursa (job #1823234) | Cod sursa (job #36507) | Cod sursa (job #2126678) | Cod sursa (job #3001862)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n, top, st[120005], viz[120005];
vector<int>ans;
struct Elem{
double x, y;
bool operator < (const Elem A) const{
if(y == A.y)
return x < A.x;
return y < A.y;
}
}a[120005];
long double Dreapta(Elem C, Elem A, Elem B){
///y-yA/yB-yA = x-xA/xB-xA
long double a = B.y - A.y;
long double b = A.x - B.x;
long double c = A.x * (A.y - B.y) + A.y * (B.x - A.x);
return a * C.x + b * C.y + c;
}
void ConvexHull(){
st[1] = 1;
top = 1;
for(int i = 2; i <= n; i++){
while(top > 1 && Dreapta(a[i], a[st[top-1]], a[st[top]]) > 0){
viz[st[top]] = 0;
top--;
}
st[++top] = i;
viz[i] = 1;
}
for(int i = 1; i <= top; i++)
ans.push_back(st[i]);
st[1] = n;
top = 1;
for(int i = n-1; i >= 1; i--)
if(!viz[i]){
while(top > 1&& Dreapta(a[i], a[st[top-1]], a[st[top]]) > 0){
viz[st[top]] = 0;
top--;
}
st[++top] = i;
viz[i] = 1;
}
for(int i = 2; i < top; i++)
ans.push_back(st[i]);
fout << ans.size() << "\n";
for(auto i : ans)
fout << fixed << setprecision(12) << a[i].x << " " << a[i].y << "\n";
}
int main()
{
fin >> n ;
for(int i = 1; i <= n; i++)
fin >> a[i].x >> a[i].y;
sort(a + 1, a + n + 1);
ConvexHull();
return 0;
}