Pagini recente » Cod sursa (job #2649087) | Arhiva de probleme | Arhiva de probleme | Arhiva de probleme | Cod sursa (job #749897)
Cod sursa(job #749897)
#include<fstream>
#include<iomanip>
#define nmax 120004
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct Punct {double x; double y;
inline void get()
{
fin >> x>>y;
}
inline void getout()
{
fout<< fixed;
fout<< setprecision(6)<<x << " " <<y <<'\n';
}
};
Punct v[nmax], sol[nmax];
int n, Nr = 2;
bool cmp(Punct A, Punct B)
{
return (A.y < B.y)|| (A.y == B.y && A.x < B.x);
}
void read()
{
fin >>n;
for(int i = 1; i <= n; i++)
v[i].get();
sort(v + 1, v + 1 + n,cmp);
}
bool semn(Punct A, Punct B, Punct C)
{
double a = A.y - B.y;
double b = B.x - A.x;
double c = B.y * A.x - B.x * A.y;
return (a * C.x + b* C.y +c) < 0;
}
void solve()
{
int i;
sol[1] = v[1];
sol[2] = v[2];
for(i = 3; i <= n; ++i)//det partea din stanga a infasuratoarei pana la cel mai inalt punct
{
while( Nr >= 2 && semn (sol[Nr - 1], sol[Nr] , v[i]) )//daca punctul e sub dreapta il scot din lista
Nr--;
sol[++Nr] = v[i];
}
for( i = n-1 ;i >= 1; --i)// det partea din dreapta
{
while(Nr >= 2 && semn(sol[Nr - 1] , sol[Nr] , v[i]) )//daca punctul e sub dreapta il scot din lista
Nr--;
sol[++Nr] = v[i];
}
Nr--;
}
int main()
{
read();
solve();
fout<<Nr <<'\n';
for(int i= 1; i <= Nr; ++i)
sol[i].getout();
fin.close();
return 0;
}