Pagini recente » Cod sursa (job #1295139) | Cod sursa (job #2182726) | Cod sursa (job #2149270) | Monitorul de evaluare | Cod sursa (job #249431)
Cod sursa(job #249431)
#include<stdio.h>
#define INF 1<<30
#include<algorithm>
using namespace std;
struct coord {long double x,y,tg;} aux,v[120111];
int p,n,i,s[120111];
long double xmin,ymin;
int poz( long double x1, long double y1, long double x2, long double y2, long double x3, long double y3 ){
long double S;
S=(x3-x1)*(y2-y1)-(x2-x1)*(y3-y1);
if(S >= 0)
return -1;
return 1;
}
int cmp(coord a, coord b){
return a.tg < b.tg;
}
int main(){
FILE *f=fopen("infasuratoare.in","r");
fscanf(f,"%d",&n);
ymin = xmin = INF;
for(i = 1; i <= n; i++){
fscanf(f,"%Lf %Lf",&v[i].x,&v[i].y);
if(v[i].x < xmin || (v[i].x == xmin && v[i].y < ymin)){
xmin = v[i].x;
ymin = v[i].y;
p=i;
}
}
fclose(f);
aux=v[n];
v[n]=v[p];
v[p]=aux;
for(i = 1; i < n; i++){
v[i].x-= xmin;
v[i].y-= ymin;
v[i].tg = v[i].y / v[i].x;
}
v[n].x-= xmin;
v[n].y-= ymin;
sort(v + 1, v + n, cmp);
s[++s[0]] = n;
for(i = 1; i < n; i++){
s[++s[0]]=i;
while(poz( v[s[s[0] - 1]].x, v[s[s[0] - 1]].y, v[s[s[0]]].x, v[s[s[0]]].y, v[s[s[0] - 2]].x, v[s[s[0] - 2]].y ) == -1 && s[0] > 2){
s[0]--;
s[s[0]] = s[s[0] + 1];
}
}
FILE *g=fopen("infasuratoare.out","w");
fprintf(g, "%d\n", s[0]);
for(i = 1; i <= s[0]; i++){
fprintf(g, "%Lf %Lf\n", v[s[i]].x + xmin, v[s[i]].y + ymin);
}
fclose(g);
return 0;
}