Pagini recente » Cod sursa (job #1084930) | Cod sursa (job #3190885) | Cod sursa (job #3150068) | Cod sursa (job #412632) | Cod sursa (job #1568821)
#include <cstdio>
#include <vector>
#define nmax 120004
#include <algorithm>
using namespace std;
typedef pair<double,double> Punct;
Punct V[nmax],S[nmax];
int N;
void interschimba(Punct &a,Punct &b){
Punct aux = a;
a = b;
b = aux;
}
inline double produsX(const Punct &a,const Punct &b,const Punct &c){
return (b.first - a.first) * (c.first - a.first) - (b. second - a.second) * (c.first - a.first);
}
inline bool cmp(const Punct &a,const Punct &b){
return produsX(V[1],a,b) < 0;
}
int main(){
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d ",&N);
int i,poz;
for(i = 1;i <= N;i++){
scanf("%lf %lf",&V[i].first,&V[i].second);
if(i == 1 || V[i].first < V[poz].first || (V[i].first == V[poz].first && V[i].second < V[poz].second))poz = i;
}
interschimba(V[1],V[poz]);
sort(V + 2,V + N + 1,cmp);
int h = 2;
S[1] = V[1];
S[2] = V[2];
for(i = 3;i <= N;i++){
while(h >= 2 && produsX(S[h-1],S[h],V[i]) > 0)--h;
S[++h] = V[i];
}
printf("%d\n",h);
for(i = h;i >= 1;i--)printf("%lf %lf\n",S[i].first,S[i].second);
printf("\n");
return 0;
}