Pagini recente » Cod sursa (job #159029) | Cod sursa (job #629832) | Cod sursa (job #1175349) | Cod sursa (job #2673906) | Cod sursa (job #2835633)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int dim=200000;
struct pt{
long double x,y;
int ind;
bool operator <(const pt &other) const
{
if(x==other.x){
return y<other.y;
}
return x<other.x;
}
}v[dim];
vector<pt>ans;
int ind;
pt CENTRU;
vector<pt>e;
long double determinat(pt A,pt B,pt C){
return A.x*B.y+B.x*C.y+C.x*A.y-B.y*C.x-C.y*A.x-A.y*B.x;
}
bool ccw(pt A,pt B,pt C){
return determinat(A,B,C)>0;
}
bool cmp(pt A,pt B){
return ccw(e[0],A,B);
}
int ap[dim],stiva[dim],vf;
bool cross(pt a,pt b,pt c){
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x)<=0;
}
void solve(){
vf=0;
for(auto it:e){
long double y=it.y;
int ind=it.ind;
while(vf>=2 && cross(v[stiva[vf-1]],v[stiva[vf]],v[ind])){
ap[stiva[vf]]--;
vf--;
}
stiva[++vf]=ind;
ap[ind]++;
}
vf=0;
reverse(e.begin(),e.end());
for(auto it:e){
long double y=it.y;
int ind=it.ind;
while(vf>=2 && cross(v[stiva[vf-1]],v[stiva[vf]],v[ind])){
ap[stiva[vf]]--;
vf--;
}
stiva[++vf]=ind;
ap[ind]++;
}
}
signed main(){
int n;
CENTRU.x=1e9,CENTRU.y=1e9,ind=0;
fin>>n;
for(int i=1;i<=n;i++){
fin>>v[i].x>>v[i].y;
e.push_back({v[i].x,v[i].y,i});
if(v[i].x<CENTRU.x){
CENTRU=v[i];
ind=i;
}
if(v[i].x==CENTRU.x){
if(v[i].y<CENTRU.y){
CENTRU=v[i];
ind=i;
}
}
}
sort(e.begin(),e.end());
solve();
for(int i=1;i<=n;i++){
if(ap[i]){
ans.push_back(v[i]);
}
}
sort(ans.begin(),ans.end(),cmp);
fout<<ans.size()<<'\n';
int ok=false;
for(auto it:ans){
if(it.x==v[ind].x&&it.y==v[ind].y){
ok=1;
}
if(ok){
fout<<fixed<<setprecision(12)<<it.x<<' '<<it.y<<'\n';
}
}
for(auto it:ans){
if(it.x==v[ind].x&&it.y==v[ind].y){
return 0;
}
if(ok){
fout<<fixed<<setprecision(12)<<it.x<<' '<<it.y<<'\n';
}
}
}