Pagini recente » Cod sursa (job #792217) | Cod sursa (job #719308) | Cod sursa (job #646938) | Cod sursa (job #536781) | Cod sursa (job #2586913)
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
ifstream fin("infasuratoare.in"); ofstream fout("infasuratoare.out");
int n;
pair<double, double> p[120000];
double cross_product( pair<double, double> &p1, pair<double, double> &p2, pair<double, double> &p3 ){
return (p2.ft-p1.ft)*(p3.sc-p2.sc)-(p3.ft-p2.ft)*(p2.sc-p1.sc);
}
int main(){
fin>>n;
int p0=0;
for(int i=0; i<n; i++){
fin>>p[i].ft>>p[i].sc;
if(p[i].sc<p[p0].sc){
p0=i;
}
}
vector<pair<double, int> > g;
g.pb(mp(-100, p0) );
for(int i=0; i<n; i++){
if(i!=p0){
g.pb( mp(atan2( (p[i].sc-p[p0].sc), (p[i].ft-p[p0].ft ) ), i) );
cout<<(p[i].sc-p[p0].sc)<<" "<<(p[i].ft-p[p0].ft )<<" "<<g[g.size()-1].ft<<"\n";
}
}
sort(g.begin(), g.end());
vector<pair<double, double>> h; h.pb(mp( p[g[0].sc].ft, p[g[0].sc].sc ) ); h.pb(mp( p[g[1].sc].ft, p[g[1].sc].sc )); h.pb(mp( p[g[2].sc].ft, p[g[2].sc].sc )); g.erase(g.begin(), g.begin()+3);
while(!g.empty()){
if(h[h.size()-2].ft==6.000 && h[h.size()-2].sc==7.000){
cout<<cross_product(h[h.size()-3], h[h.size()-2], h[h.size()-1])<<"crs\n";
}
while(cross_product(h[h.size()-3], h[h.size()-2], h[h.size()-1])<=0 ){
h.erase(h.begin()+h.size()-2, h.begin()+h.size()-1);
}
h.pb(mp( p[g[0].sc].ft, p[g[0].sc].sc ));
g.erase(g.begin(), g.begin()+1);
cout<<h.size()<<" ";
}
cout<<"\n";
while(cross_product(h[h.size()-3], h[h.size()-2], h[h.size()-1])<=0 ){
h.erase(h.begin()+h.size()-2, h.begin()+h.size()-1);
}
fout<<h.size()<<"\n";
for(int i=0; i<h.size(); i++){
fout<<h[i].ft<<" "<<h[i].sc<<"\n";
}
return 0;
}