Pagini recente » Istoria paginii runda/10thgraders | Cod sursa (job #1483156) | Cod sursa (job #2100713) | Cod sursa (job #1028830) | Cod sursa (job #377668)
Cod sursa(job #377668)
#include <fstream>
#include <algorithm>
#define MAX 120010
#define cx first
#define cy second
using namespace std;
pair<double,double> v[MAX];
int puncte[MAX];
int N,pstart,xref,yref;
int st[MAX];
inline bool cmp(int p1,int p2){
return ((long double)(v[p1].cy-yref)*(v[p2].cx-xref)<(long double)(v[p1].cx-xref)*(v[p2].cy-yref));
}
inline bool good_turn(int p1,int p2,int p3){
long double produs=(long double)(v[p1].cx)*(v[p2].cy)+(long double)(v[p2].cx)*(v[p3].cy)+(long double)(v[p3].cx)*(v[p1].cy)
-(long double)(v[p1].cx)*(v[p3].cy)-(long double)(v[p3].cx)*(v[p2].cy)-(long double)(v[p2].cx)*(v[p1].cy);
if (produs>0) return true; else return false;
}
int main(){
pstart=xref=yref=0;
ifstream fi("infasuratoare.in");
fi>>N;
for (int i=1;i<=N;++i){
fi>>v[i].cx>>v[i].cy;
if (pstart==0 || (v[i].cx<xref) || (v[i].cx==xref && v[i].cy<yref)) { pstart=i; xref=v[i].cx; yref=v[i].cy; }
}
fi.close();
--xref;
int NP=0;
for (int i=1;i<=N;++i) if (i!=pstart) puncte[++NP]=i;
sort(puncte+1,puncte+NP+1,cmp);
int vf=1;
st[1]=pstart;
for (int i=1;i<=NP;++i){
while (vf>=2 && good_turn(st[vf-1],st[vf],puncte[i])==false) --vf;
st[++vf]=puncte[i];
}
ofstream fo("infasuratoare.out");
fo<<vf<<"\n";
fo.precision(22);
for (int i=1;i<=vf;++i) fo<<v[st[i]].cx<<" "<<v[st[i]].cy<<"\n";
fo.close();
return 0;
}