Pagini recente » Cod sursa (job #9312) | Cod sursa (job #266857) | Cod sursa (job #2621490) | Cod sursa (job #22003) | Cod sursa (job #893229)
Cod sursa(job #893229)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
FILE *f=fopen("infasuratoare.in","r"),*g=fopen("infasuratoare.out","w");
struct type
{
double tan,x,y;
};
const int maxn=120006,inf=2000000000;
type punct[maxn];
int n,i,poz,ind[maxn];
double p0x,p0y;
vector <int> sol;
bool cmp(int a,int b)
{
double x=punct[a].tan,y=punct[b].tan;
if(x<y)
return true;
return false;
}
double unghi( type a)
{
double u=a.x-p0x,v=a.y-p0y;
return double(atan(v/u));
}
void read()
{
fscanf(f,"%d",&n);
p0x=p0y=inf;
for(i=1;i<=n; i++)
{
fscanf(f,"%lf%lf",&punct[i].x,&punct[i].y);
ind[i]=i;
if(punct[i].x<p0x || (punct[i].x==p0x && punct[i].y<p0y) )
{
p0x=punct[i].x;
p0y=punct[i].y;
poz=i;
}
}
punct[poz].tan=-inf;
for(i=1;i<=n;i++)
if(i!=poz)
punct[i].tan=unghi(punct[i]);
sort( ind+1 , ind+n+1 , cmp );
}
int deter( int i , int j , int k )
{
double val;
val = (punct[i].x*punct[j].y) + (punct[j].x*punct[k].y) + (punct[k].x*punct[i].y);
val -= ( (punct[k].x*punct[j].y) + (punct[j].x*punct[i].y) + (punct[i].x*punct[k].y) );
return val;
}
void write()
{
for(i=0;i<sol.size();i++)
fprintf(g,"%lf %lf\n",punct[sol[i]].x,punct[sol[i]].y);
}
int main()
{
read();
sol.push_back(poz);
sol.push_back(ind[2]);
sol.push_back(ind[3]);
for(i=4;i<=n;i++)
{
while(deter(sol[sol.size()-2],sol[sol.size()-1],ind[i])<0)
sol.pop_back();
sol.push_back(ind[i]);
}
write();
return 0;
}