Pagini recente » Cod sursa (job #1246340) | Cod sursa (job #2877825) | Cod sursa (job #3131464) | Cod sursa (job #961343) | Cod sursa (job #1537552)
#include<fstream>
#include<algorithm>
#include<iomanip>
#define x first
#define y second
using namespace std;
ifstream in ("infasuratoare.in");
ofstream out("infasuratoare.out");
int n,top,pos,s[120010];
typedef pair <double,double> punct;
punct t[120010];
double determinant(punct a, punct b, punct c){
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
bool cmp(punct a,punct b){
return (determinant(t[1],a,b)<0);
}
int main(){
in>>n;
pos=1;
for(int i=0 ; i<n ; i++){
in>>t[i].x>>t[i].y;
if(t[i]<t[pos])
pos=i;
}
swap(t[1],t[pos]);
sort(t+1,t+n-1,cmp);
s[++top]=1;
for( int i=1 ; i<n ; i++ ){
while(top>0 && determinant(t[s[top-1]],t[s[top]],t[1])>0)
top--;
s[++top]=i;
}
out<<top+1<<"\n";
while(top){
out<<fixed<<setprecision(6)<<t[s[top]].x<<" "<<t[s[top]].y<<"\n";
top--;
}
out.close();
return 0;
}