Pagini recente » Cod sursa (job #2799974) | Cod sursa (job #2162519) | Cod sursa (job #1903874) | Cod sursa (job #218778) | Cod sursa (job #3247493)
#include <stdio.h>
#include <algorithm>
#define MAXN 120000
using namespace std;
struct point{
double x, y;
};
point puncte[MAXN];
point my_stack_left[MAXN+1], my_stack_right[MAXN+1];
int stack_pointer_left, stack_pointer_right;
bool cmp(const point&a, const point &b){
if(a.y==b.y)
return a.x<b.x;
return a.y<b.y;
}
bool AreaIsPositive(point a, point b, point c){
return a.x*b.y+b.x*c.y+c.x*a.y-c.x*b.y-a.x*c.y-b.x*a.y>0;
}
void my_push_back(point p, bool stanga){
if(stanga)
my_stack_left[++stack_pointer_left]=p;
else
my_stack_right[++stack_pointer_right]=p;
}
void my_pop(bool stanga){
if(stanga)
stack_pointer_left--;
else
stack_pointer_right--;
}
int my_size(bool stanga){
if(stanga)
return stack_pointer_left;
else
return stack_pointer_right;
}
int main()
{
FILE *fin, *fout;
int n, i;
fin=fopen("infasuratoare.in", "r");
fscanf(fin, "%d", &n);
for(i=0;i<n;i++){
fscanf(fin, "%lf%lf", &puncte[i].x, &puncte[i].y);
}
fclose(fin);
sort(puncte, puncte+n, cmp);
my_push_back(puncte[0], 0);
my_push_back(puncte[0], 1);
stack_pointer_left=stack_pointer_right=1;
for(i=1;i<n-1;i++){
///stanga==1
if(AreaIsPositive(puncte[0], puncte[n-1], puncte[i])){///lucrez cu stiva din stanga
while(my_size(1)>1&&AreaIsPositive(my_stack_left[stack_pointer_left-1], my_stack_left[stack_pointer_left], puncte[i])){
my_pop(1);
}
my_push_back(puncte[i], 1);
}
else{///lucrez cu stiva din dreapta
while(my_size(0)>1&&!AreaIsPositive(my_stack_right[stack_pointer_right-1], my_stack_right[stack_pointer_right], puncte[i])){
my_pop(0);
}
my_push_back(puncte[i], 0);
}
}
///verific daca nu cumva mai trebuie sa scot puncte datorita celui mai de sus punct
while(my_size(1)>1&&AreaIsPositive(my_stack_left[stack_pointer_left-1], my_stack_left[stack_pointer_left], puncte[n-1])){
my_pop(1);
}
while(my_size(0)>1&&!AreaIsPositive(my_stack_right[stack_pointer_right-1], my_stack_right[stack_pointer_right], puncte[n-1])){
my_pop(0);
}
fout=fopen("infasuratoare.out", "w");
fprintf(fout, "%d\n", stack_pointer_left+stack_pointer_right);
for(i=1;i<=stack_pointer_right;i++){
fprintf(fout, "%.12lf %.12lf\n", my_stack_right[i].x, my_stack_right[i].y);
}
fprintf(fout, "%.12lf %.12lf\n", puncte[n-1].x, puncte[n-1].y);
for(i=stack_pointer_left;i>1;i--){
fprintf(fout, "%.12lf %.12lf\n", my_stack_left[i].x, my_stack_left[i].y);
}
fclose(fout);
return 0;
}