Pagini recente » Cod sursa (job #1791304) | Cod sursa (job #541320) | Cod sursa (job #583113) | Cod sursa (job #2615161) | Cod sursa (job #2953610)
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
const int MAX_N=120000;
struct XY{
double x,y;
};
XY v[MAX_N];
vector <XY> hull;
int n;
inline double orientation(const XY& a, const XY& b, const XY& c){
return (b.y-a.y)*(c.x-b.x)-(b.x-a.x)*(c.y-b.y);
}
bool cmp(const XY& a,const XY& b){
return orientation(v[0],a,b)<0;
}
int findfirst(){
int j=0,i;
for(i=1;i<n;i++){
if(v[j].y<v[i].y || (v[j].y==v[i].y && v[j].x>v[i].x))
j=i;
}
return j;
}
void comphull(){
int i;
hull.push_back(v[0]);
hull.push_back(v[1]);
for(i=2;i<n;i++){
while(hull.size()>=2 && orientation(hull[hull.size()-2],hull.back(),v[i])>=0)
hull.pop_back();
hull.push_back(v[i]);
}
}
int main(){
FILE *fin,*fout;
fin=fopen("infasuratoare.in","r");
fout=fopen("infasuratoare.out","w");
fscanf(fin,"%d",&n);
for(int i=0;i<n;i++){
fscanf(fin,"%lf%lf",&v[i].x,&v[i].y);
}
swap(v[0],v[findfirst()]);
sort(v+1,v+n,cmp);
comphull();
fprintf(fout,"%d\n", hull.size());
for(auto k:hull)
fprintf(fout,"%.12lf %.12lf\n", k.x,k.y);
fclose(fin);
fclose(fout);
return 0;
}