Pagini recente » Cod sursa (job #828977) | Cod sursa (job #1145754) | Cod sursa (job #2432551) | Cod sursa (job #1639379) | Cod sursa (job #2101736)
#include <cstdio>
#include <algorithm>
using namespace std;
FILE *f = fopen("infasuratoare.in","r");
FILE *g = fopen("infasuratoare.out","w");
struct punct{
double x,y;
bool operator < (const punct &other)const{
if(x != other.x){
return x < other.x;
}
return y < other.y;
}
};
double det(punct a,punct b,punct c){
return a.x * b.y - a.x * c.y + b.x * c.y - b.x * a.y + c.x *a.y - c.x * b.y;
}
punct hull[120005];
punct V[120005];
int N,len;
int main(){
fscanf(f,"%d",&N);
for(int i = 1;i <= N;i++){
fscanf(f,"%lf %lf",&V[i].x,&V[i].y);
}
sort(V + 1,V + 1 + N);
for(int i = 1;i <= N;i++){
while(len > 1 && det(hull[len - 1],hull[len],V[i]) < 0){
len--;
}
hull[++len] = V[i];
}
reverse(V + 1,V + 1 + N);
for(int i = 2;i <= N;i++){
while(len > 1 && det(hull[len - 1],hull[len],V[i]) < 0){
len--;
}
hull[++len] = V[i];
}
len--;
fprintf(g,"%d\n",len);
for(int i = 1;i <= len;i++){
fprintf(g,"%.6f %.6f\n",hull[i].x,hull[i].y);
}
fclose(f);
fclose(g);
return 0;
}