Pagini recente » Cod sursa (job #2739461) | Cod sursa (job #3213755) | Cod sursa (job #901150) | Cod sursa (job #2575741) | Cod sursa (job #1830112)
#include <bits/stdc++.h>
#define INF 1e9
#define NMAX 120005
using namespace std;
struct point{
double x,y;
};
point V[NMAX];
int sol[NMAX];
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
inline double unghiularpoint(point a,point b,point c){
return (b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x);
}
struct cmp{
int operator()(const point &a,const point &b){
return unghiularpoint(V[1],a,b) > 0;
}
};
int main()
{
ios :: sync_with_stdio(false);
fin.tie(NULL);
int n,poz = 1,top = 0;
fin >> n;
for(int i = 1; i <= n; i++){
fin >> V[i].x >> V[i].y;
if(V[i].x < V[poz].x)
poz = i;
if(V[i].x == V[poz].x && V[i].y < V[poz].y)
poz = i;
}
swap(V[1],V[poz]);
sort(V + 2,V + n + 1, cmp());
V[n + 1] = V[1];
sol[++top] = 1;
for(int i = 2; i <= n; i++){
sol[++top] = i;
while(unghiularpoint(V[sol[top - 1]],V[sol[top]],V[i + 1]) < 0)
top--;
}
fout << top << "\n";
for(int i = 1; i <= top; i++)
fout << setprecision(6) << fixed << V[sol[i]].x << " " << V[sol[i]].y << "\n";
return 0;
}