Pagini recente » Cod sursa (job #1235546) | Cod sursa (job #483464) | Cod sursa (job #1182068) | Cod sursa (job #295340) | Cod sursa (job #1537575)
#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=1 ; i<=n ; i++){
in>>t[i].x>>t[i].y;
if(t[i]<t[pos])
pos=i;
}
swap(t[1],t[pos]);
sort(t+2,t+n+1,cmp);
s[++top]=1;
for( int i=2 ; i<=n ; i++ ){
while(top>1 && determinant(t[s[top-1]],t[s[top]],t[i])>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;
}