Pagini recente » Cod sursa (job #2466720) | Cod sursa (job #1854370) | Cod sursa (job #1467006) | Cod sursa (job #2189612) | Cod sursa (job #832258)
Cod sursa(job #832258)
#include<fstream>
#include<iostream>
#include <algorithm>
using namespace std;
struct Punct{double x,y;};
Punct stack[1000];
int k;
bool cmp(Punct a,Punct b){
if(a.y<b.y)
return true;
if(a.y==b.y && a.x<b.x)
return true;
return false;
}
int semn(Punct a , Punct b, Punct c)
{
if((b.x * c.y + a.x * b.y + c.x * a.y- a.y * b.x - c.x * b.y - a.x * c.y) >=0) return 1;
else return 0;
}
void infas(Punct a[1000],int n){
int i;
sort(a+1 , a + n + 1, cmp);
stack[1]=a[1];
k = 1;
for(i = 2; i <= n; i++)
{
while(k > 1 && !semn(stack[k-1], stack[k], a[i])) k--;
stack[++k]=a[i];
}
for(i = n - 1; i >= 1; i--)
{
while(!semn(stack[k-1], stack[k], a[i]))k--;
stack[++k]=a[i];
}
}
int main()
{
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
Punct a[100];
int n;
f>>n;
int i;
for(i=1;i<=n;i++){
f>>a[i].x>>a[i].y;
}
infas(a,n);
g<<k-1<<"\n";
for(i=1;i<k;i++){
g<<stack[i].x<<" "<<stack[i].y<<"\n";
}
return 0;
}