Pagini recente » Cod sursa (job #849591) | Cod sursa (job #2356528) | Cod sursa (job #1105346) | Cod sursa (job #2907934) | Cod sursa (job #2953604)
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#define MAXN 120004
#define ERROR 0.000000000001
using namespace std;
struct XY{
double x,y;
};
XY v[MAXN];
XY comp;
vector <XY> q;
bool cmp(XY a,XY b){
if((a.y-comp.y)*(b.x-comp.x)<(b.y-comp.y)*(a.x-comp.x)){
return 1;
}else{
if((a.y-comp.y)*(b.x-comp.x)>(b.y-comp.y)*(a.x-comp.x)){
return 0;
}else{
if(a.x<b.x){
return 1;
}else{
return 0;
}
}
}
}
bool verf(XY a,XY b,XY c){
int aux=(b.y-a.y)*(c.x-b.x)-(b.x-a.x)*(c.y-b.y);
if(aux>0){
return 0;
}
return 1;
}
int main(){
int n,i;
FILE *fin,*fout;
fin=fopen("infasuratoare.in","r");
fout=fopen("infasuratoare.out","w");
fscanf(fin,"%d",&n);
comp.x=-10000000000;
for(i=0;i<n;i++){
fscanf(fin,"%lf%lf",&v[i].x,&v[i].y);
if(comp.x<v[i].x){
comp=v[i];
}
}
sort(v,v+n,cmp);
q.push_back(comp);
q.push_back(v[0]);
for(i=1;i<n-1;i++){
while(verf(q[q.size()-2],q.back(),v[i])==0){
q.pop_back();
}
q.push_back(v[i]);
}
fprintf(fout,"%d\n",q.size());
for(i=0;i<q.size();i++){
fprintf(fout,"%lf %lf\n",q[i].x,q[i].y);
}
fclose(fin);
fclose(fout);
return 0;
}