Pagini recente » Cod sursa (job #2337506) | Cod sursa (job #423144) | Cod sursa (job #2075990) | Cod sursa (job #2899924) | Cod sursa (job #2173216)
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
double minx, miny, maxx, maxy;
struct ic{double x, y;};
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, stg, j;
int 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;
drx.push_back(v[1].x);
dry.push_back(v[1].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=1;
st[0]=0;
st[1]=1;
for(i=2;i<drx.size();i++){
st[++k]=i;
if(dry[st[k-1]]<dry[st[k]]){
miny=dry[st[k-1]];
minx=drx[st[k-1]];
maxx=drx[st[k]];
maxy=dry[st[k]];
}
else{
maxy=dry[st[k-1]];
maxx=drx[st[k-1]];
minx=drx[st[k]];
miny=dry[st[k]];
}
if(arie(drx[i], dry[i])>= 0)
k--;
}
for(i=stgx.size()-1;i>=0;i--){
if(stgy[st[k-1]]<stgy[st[k]]){
miny=stgy[st[k-1]];
minx=stgx[st[k-1]];
maxx=stgx[st[k]];
maxy=stgy[st[k]];
}
else{
maxy=dry[st[k-1]];
maxx=drx[st[k-1]];
minx=drx[st[k]];
miny=dry[st[k]];
}
if(arie(v[i].x, v[i].y)<= 0)
st[k]=i;
else
st[++k]=i;
}
for(j=0;j<=k;j++){
fprintf(fout,"%lf %lf\n", v[st[k]].x, v[st[k]].y);
}
fclose(fin);
fclose(fout);
return 0;
}