Pagini recente » Cod sursa (job #1784761) | Cod sursa (job #1575607) | Cod sursa (job #2236378) | Cod sursa (job #585043) | Cod sursa (job #2196169)
#include <iostream>
#include<stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
struct ic{double x, y;};
ic rez [120001];
int minx, miny, maxx, maxy;
double arie(double qx, double qy){
return (minx - qx) * (maxy - qy) - (miny - qy) * (maxx - qx);
}
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;
ic v[120001];
int i, j, ii, jj, n, h, lg, cont;
vector <double> drx, dry, stgx, stgy;
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);
drx.push_back(v[1].x);
dry.push_back(v[1].y);
for(i=2;i<=n-1;i++){
h=drx.size()-1;
minx=v[1].x;
miny=v[1].y;
maxx=v[n].x;
maxy=v[n].y;
if(arie(v[i].x, v[i].y) < 0){
if(h>=1){
minx=drx[h-1];
miny=dry[h-1];
maxx=drx[h];
maxy=dry[h];
while(arie(v[i].x, v[i].y) <= 0&&h>=1){
drx.pop_back();
dry.pop_back();
h--;
minx=drx[h-1];
miny=dry[h-1];
maxx=drx[h];
maxy=dry[h];
}
}
drx.push_back(v[i].x);
dry.push_back(v[i].y);
}
}
stgx.push_back(v[n].x);
stgy.push_back(v[n].y);
for(i=n-1;i>=2;i--){
h=stgx.size()-1;
minx=v[n].x;
miny=v[n].y;
maxx=v[1].x;
maxy=v[1].y;
if(arie(v[i].x, v[i].y) < 0){
if(h>=1){
minx=stgx[h-1];
miny=stgy[h-1];
maxx=stgx[h];
maxy=stgy[h];
while(arie(v[i].x, v[i].y) <= 0&&h>=1){
stgx.pop_back();
stgy.pop_back();
h--;
minx=stgx[h-1];
miny=stgy[h-1];
maxx=stgx[h];
maxy=stgy[h];
}
}
stgx.push_back(v[i].x);
stgy.push_back(v[i].y);
}
}
i=drx.size()-1;
j=stgx.size()-1;
ii=0;
jj=0;
cont=0;
fprintf(fout,"%d\n", drx.size()+stgx.size());
for(i=0;i<=drx.size()-1;i++){
fprintf(fout,"%lf %lf\n", drx[i], dry[i]);
}
for(i=0;i<=stgx.size()-1;i++){
fprintf(fout,"%lf %lf\n", stgx[i], stgy[i]);
}
fclose(fin);
fclose(fout);
return 0;
}