Pagini recente » Cod sursa (job #400932) | Cod sursa (job #2459833) | Cod sursa (job #2120438) | Cod sursa (job #1551104) | Cod sursa (job #2759954)
#include <bits/stdc++.h>
#define f double
#define x first
#define y second
#define pi 3.14159
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
pair<f,f> sj={-1,-1};
f angleTo( pair<f,f> o, pair<f,f> p)
{
return atan2(p.y-o.y,p.x-o.x);
}
f orietation(pair<f,f> a, pair<f,f> b, pair<f,f> c)
{
return (b.y-a.y)*(c.x-b.x)-(c.y-b.y)*(b.x-a.x);
}
bool cmp(const pair<f,f> &a, const pair<f,f> &b)
{
return (angleTo(sj,a)<angleTo(sj,b))||(angleTo(sj,a)==angleTo(sj,b)&&a.x<b.x);
}
vector<pair<f,f> > infas(vector<pair<f,f> > v)
{
sort(v.begin(),v.end(),cmp);
vector<pair<f,f> > ans;
cout<<sj.x<<','<<sj.y<<'\n';
for(int i=0;i<v.size();i++)
cout<<v[i].x<<','<<v[i].y<<' ';
cout<<'\n';
ans.push_back(sj); ans.push_back(v[0]);
for(int i=1;i<v.size();i++)
{
pair<f,f> p1=ans[ans.size()-2],p2=ans[ans.size()-1];
while(ans.size()>1&&orietation(p1,p2,v[i])>0)
{
cout<<p1.x<<','<<p1.y<<' '<<p2.x<<','<<p2.y<<' '<<v[i].x<<','<<v[i].y<<' '<<orietation(p1,p2,v[i])<<'\n';
ans.pop_back();
p2=p1;
if(ans.size()>1) p1=ans[ans.size()-2];
}
ans.push_back(v[i]);
}
return ans;
}
int main()
{
int n;
vector<pair<f,f> > pts;
int sjpos;
in>>n;
for(int i=0;i<n;i++)
{
pair<f,f> pt;
in>>pt.x>>pt.y;
pts.push_back(pt);
if(pt.x<sj.x||i==0) {sj=pt; sjpos=i;}
if(pt.x==sj.x&&pt.y<sj.y) {sj=pt; sjpos=i;}
}
for(int i=0;i<n;i++)
{
if(i>sjpos) pts[i-1]=pts[i];
}
pts.pop_back();
pts=infas(pts);
out<<pts.size()<<'\n';
for(int i=0;i<pts.size();i++)
{
out<<fixed<<setprecision(6)<<pts[i].x<<' '<<pts[i].y<<'\n';
}
return 0;
}