Pagini recente » Cod sursa (job #1507555) | Cod sursa (job #2725819) | Cod sursa (job #513448) | Cod sursa (job #879486) | Cod sursa (job #2176058)
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
double minx, miny, maxx, maxy;
struct ic{double x, y;};
struct stiva{int poz, afis;};
double arie(double qx, double qy){
return (minx*maxy+maxx*qy+qx*miny-qx*maxy-maxx*miny-minx*qy)/2;
}
bool cmp(ic a, ic b){
if(a.y < b.y)
return true;
else{
if(a.y==b.y){
if(a.x<b.x)
return true;
else
return false;
}
else
return false;
}
}
int main() {
FILE *fin, *fout;
int n, i, k, j, cant;
stiva st[100000];
ic v[10000];
vector <double> stgx, stgy, drx, dry;
fin = fopen("infasuratoare.in", "r");
fout = fopen("infasuratoare.out", "w");
fscanf(fin,"%d", &n);
for(i=1;i<=n;i++){
fscanf(fin,"%lf%lf", &v[i].x, &v[i].y);
}
sort(v+1, v+n+1, cmp);
minx=v[1].x;
miny=v[1].y;
maxx=v[n].x;
maxy=v[n].y;
for(i=1;i<=n;i++){
if(arie(v[i].x, v[i].y)<=0){
drx.push_back(v[i].x);
dry.push_back(v[i].y);
}
if(arie(v[i].x, v[i].y)>=0){
stgx.push_back(v[i].x);
stgy.push_back(v[i].y);
}
}
k=0;
st[0].poz=0;
for(i=1;i<drx.size();i++){
cant=drx.size();
miny=dry[st[k].poz];
minx=drx[st[k].poz];
maxx=drx[i+1];
maxy=dry[i+1];
if(arie(drx[i], dry[i]) < 0){
st[++k].poz=i;
st[k].afis=1;
}
}
for(i=stgx.size()-2;i>=1;i--){
maxy=stgy[st[k].poz];
maxx=stgx[st[k].poz];
minx=stgx[i-1];
miny=stgy[i-1];
if(arie(stgx[i], stgy[i]) > 0){
st[++k].poz=i;
st[k].afis=0;
}
}
fprintf(fout,"%d\n", k+1);
for(j=0;j<=k;j++){
if(st[j].afis==1)
fprintf(fout,"%f %f\n", drx[st[j].poz],dry[st[j].poz]);
else
fprintf(fout,"%f %f\n", stgx[st[j].poz],stgy[st[j].poz]);
}
fclose(fin);
fclose(fout);
return 0;
}