Pagini recente » Cod sursa (job #2494083) | Cod sursa (job #787554) | Cod sursa (job #1383285) | Cod sursa (job #319780) | Cod sursa (job #872181)
Cod sursa(job #872181)
#include<fstream>
#include<algorithm>
#include<string.h>
#define DIM 120010
using namespace std;
ifstream f("infasuratoare.in");
FILE*g=fopen("infasuratoare.out","w");
int n;
double X_min , Y_min;
struct punct{
double x ;
double y;
}V[DIM],aux;
void swap(int x){
aux=V[x];
V[x]=V[n];
V[n]=aux;
}
void read(){
f>>n;
int i , p_min=1;
for(i=1;i<=n;i++){
f>>V[i].x>>V[i].y;
if(V[i].y<V[p_min].y)
p_min=i;
else if(V[i].y==V[p_min].y)
if(V[i].x<V[p_min].x)
p_min=i;
}
swap(p_min);
X_min=V[n].x;Y_min=V[n].y;
n--;
}
int cmp(punct a , punct b){
double p1=a.y*b.x;
double p2=b.y*a.x;
if(p1>p2)
return 0;
return 1;
}
long double semn(punct a, punct b , punct c){
return ((long double)b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
void infasuratoare(){
int S[DIM];
int vf=2 , i;
memset(S,0,sizeof(S));S[vf]=1;
for(i=2;i<=n;i++){
while(semn(V[S[vf-1]],V[S[vf]],V[i])<=0&&vf>=1){
vf--;
}
S[++vf]=i;
}
fprintf(g,"%d\n",vf);
for(i=1;i<=vf;i++)
fprintf(g,"%.6f %.6f \n",V[S[i]].x+X_min,V[S[i]].y+Y_min);
}
int main(){
read();
for(int i=1;i<=n;i++){
V[i].x-=X_min;
V[i].y-=Y_min;
}
sort(V+1,V+n+1,cmp);
infasuratoare();
return 0;
}