Pagini recente » Monitorul de evaluare | Rating Zaharia Andreea (andreea_zaha) | Cod sursa (job #2009087) | Cod sursa (job #1401943) | Cod sursa (job #639840)
Cod sursa(job #639840)
#include <stdio.h>
#include <fstream>
using namespace std;
struct punct{double x,y;};
int varf,crt,n;
punct v[120001],stiva[120001],prim;
FILE *f=fopen("infasuratoare.in","r");
inline double panta(punct a){return (a.y-prim.y)/(a.x-prim.x);};
inline bool maijos(punct a, punct b){if (panta(a)<panta(b)) return 1; else return 0;}
inline double determinant(punct unu, punct doi, punct trei){
return (unu.x*doi.y+doi.x*trei.y+trei.x*unu.y-unu.x*trei.y-doi.x*unu.y-trei.x*doi.y);}
void adaugare(){
if (determinant(stiva[varf-1],stiva[varf],v[crt])<0){
varf--;
adaugare();
}
else{
stiva[++varf]=v[crt++];
if (crt>n) return;
adaugare();
}
}
void merge(int min, int med, int max)
{
int i=min;
int j=med+1;
int k=min;
punct b[120001];
while((i<=med) && (j<=max))
{
if (maijos(v[i],v[j]))
{
b[k++]=v[i++];
}
else
{
b[k++]=v[j++];
}
}
if (j>max)
while (i<=med)
{
b[k]=v[i];
i++;
k++;
}
else
while (j<=max)
{
b[k]=v[j];
j++;
k++;
}
for (int i=min;i<=max;i++)
v[i]=b[i];
}
void merge_sort(int minimum,int maximum)
{
if (minimum<maximum)
{
int medium=(minimum+maximum)/2;
merge_sort(minimum,medium);
merge_sort(medium+1,maximum);
merge(minimum,medium,maximum);
}
}
void citire(){
int unde=1;
punct aux;
fscanf(f,"%d ",&n);
fscanf(f,"%Lf %Lf ",&v[1].x,&v[1].y);
prim=v[1];
for (int i=2;i<=n;i++){
fscanf(f,"%Lf %Lf ",&v[i].x,&v[i].y);
if (v[i].x<prim.x){prim=v[i];unde=i;}
if (v[i].x==prim.x && v[i].y<prim.y){prim=v[i];unde=i;}
}
// system("PAUSE");
// for (int j=1;j<=n;j++)
// printf("%.6Lf %.6Lf \n",v[j].x,v[j].y);
// printf("%.6Lf %.6Lf \n",prim.x,prim.y);
// system("PAUSE");
aux=v[1]; v[1]=prim; v[unde]=aux;
fclose(f);
}
int main()
{
freopen("infasuratoare.out","w",stdout);
citire();
merge_sort(2,n);
stiva[1]=v[1];
stiva[2]=v[2];
varf=2;
crt=3;
adaugare();
/* ofstream fout("infasuratoare.out");
fout.setf(ios::floatfield);
fout.precision(12);
fout<<fixed;
fout<<varf<<"\n"; */
printf("%d\n",varf);
for (int i=1;i<=varf;i++)
// fout<<stiva[i].x<<" "<<stiva[i].y<<"\n";
printf("%lf %lf\n",stiva[i].x,stiva[i].y);
// fout.close();
return 0;
}