Pagini recente » Cod sursa (job #2830684) | Cod sursa (job #514418) | Cod sursa (job #301150) | Cod sursa (job #668963) | Cod sursa (job #2953620)
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#define MAXN 120004
#define ERROR 0.000000000001
using namespace std;
struct XY{
double x,y;
};
XY v[MAXN];
XY comp;
vector <XY> q;
int verf(XY a,XY b,XY c){
return (b.y-a.y)*(c.x-b.x)-(b.x-a.x)*(c.y-b.y);
}
bool cmp(XY a,XY b){
return verf(comp,a,b)<0;
}
int main(){
int n,i;
FILE *fin,*fout;
fin=fopen("infasuratoare.in","r");
fout=fopen("infasuratoare.out","w");
fscanf(fin,"%d",&n);
comp.y=10000000000;
for(i=0;i<n;i++){
fscanf(fin,"%lf%lf",&v[i].x,&v[i].y);
if(comp.x>v[i].x){
comp=v[i];
}
}
sort(v,v+n,cmp);
q.push_back(comp);
q.push_back(v[0]);
for(i=1;i<n;i++){
while(verf(q[2],q.back(),v[i])==0 && q.size()>1){
q.pop_back();
}
q.push_back(v[i]);
}
fprintf(fout,"%d\n",q.size());
for(i=0;i<q.size();i++){
fprintf(fout,"%.12lf %.12lf\n",q[i].x,q[i].y);
}
fclose(fin);
fclose(fout);
return 0;
}