Pagini recente » Cod sursa (job #2617521) | Cod sursa (job #2109500)
#include<bits/stdc++.h>
using namespace std;
struct trips
{
double x, y;
int idx;
trips(double x, double y, double idx){
this->x = x;
this->y = y;
this->idx = idx;
}
trips(){
x = y = idx = 0;
}
bool operator<(trips other) const{
if(x == other.x)
return y < other.y;
return x < other.x;
}
};
vector <trips> G;
int t, n;
trips piv;
vector <trips> S;
void Read()
{
scanf("%d", &n);
double x, y;
for(int i = 1; i <= n; i++){
scanf("%lf %lf", &x, &y);
G.push_back(*(new trips(x, y, i)));
}
}
bool cmp(trips a, trips b)
{
double da, db;
da = (a.y - piv.y) / (a.x - piv.x);
db = (b.y - piv.y) / (b.x- piv.x);
if(abs(da - db) < 1E-17){
return (a.x - piv.x) < (b.x - piv.x);
}
return da < db;
}
double CCW(trips a, trips b, trips p)
{
return (p.y - a.y)*(b.x - a.x) - (p.x - a.x)*(b.y - a.y);
}
bool cmpid(trips a, trips b)
{
return a.idx < b.idx;
}
void Solve()
{
nth_element(G.begin(), G.begin(), G.end());
piv = G.front();
S.push_back(G.front());
sort(G.begin() + 1, G.end(), cmp);
S.push_back(G[1]);
vector <trips>::iterator it;
double ret;
for(it = G.begin() + 2; it != G.end(); it++){
ret = CCW(*(S.end() - 2), S.back(), *it);
while(ret < 1E-16){
S.pop_back();
if(S.size() == 1)
break;
ret = CCW(*(S.end() - 2), S.back(), *it);
}
S.push_back(*it);
}
printf("%d\n", S.size());
for(auto i : S)
printf("%.6lf %.6lf\n", i.x, i.y);
printf("\n");
}
void CleanUp()
{
S.clear();
G.clear();
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
Read();
Solve();
CleanUp();
return 0;
}