Pagini recente » Cod sursa (job #411165) | Cod sursa (job #1693276) | Cod sursa (job #2126072) | Cod sursa (job #150837) | Cod sursa (job #1689015)
#include <bits/stdc++.h>
#define NMax 120005
#define INF 0x3f3f3f3f
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct punct{
double x,y;
}v[NMax],s[NMax];
int n,top,index;
double unghi(punct A, punct B, punct C){
return ((B.y - A.y) * (C.x - A.x) - (C.y - A.y)*(B.x - A.x));
}
bool cmp(punct x, punct y){
return (unghi(v[1],x,y) > 0);
}
int main()
{
f >> n;
index = 0;v[index].x = INF; v[index].y = INF;
for(int i = 1; i <= n; ++i){
f >> v[i].x >> v[i].y;
if(v[index].x == v[i].x && v[index].y > v[index].y){
index = i;
}
if(v[index].x > v[i].x){
index = i;
}
}
swap(v[index],v[1]);
sort(v + 2, v + 1 + n,cmp);
s[++top] = v[1];
s[++top] = v[2];
for(int i = 3; i <= n; ++i){
while(unghi(s[top - 1],s[top],v[i]) < 0){
top--;
}
s[++top] = v[i];
}
g << top << '\n';
for(int i = top; i >= 1; --i){
g <<fixed<<setprecision(6)<< s[i].x << ' ' << s[i].y << '\n';
}
return 0;
}