Pagini recente » Cod sursa (job #3318295) | Cod sursa (job #1096604) | Cod sursa (job #3303787) | Cod sursa (job #3312054) | Cod sursa (job #3335954)
// Copilot-Addressed Rules:
// RULE: There shouldnt be any spaces in the code, except after commas.
// RULE: All variables in main should be declared globally, and can be used before they are defined.
// RULE: All open curly braces should be placed on the same line as the function or control structure they belong to, not on the line after.
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in"); //strudel
ofstream fout("infasuratoare.out"); //infasuratoare
long long x,y,n,i,inf=1e9,j;
double vx=1e10,vy=1e10;
struct pct{
double x,y;
double p,d;
long long cad;
};
pct a[120010];
stack<long long> s,st;
long long cad(double x, double y){
if(x>=0) return 1;
return 2;
}
bool cmp(pct a, pct b){
return a.cad<b.cad ||
a.cad==b.cad && a.p<b.p ||
a.cad==b.cad && a.p==b.p && a.d>b.d;
}
double det(long long x, long long y, long long z){
return a[x].x*(a[y].y-a[z].y)+a[x].y*(a[z].x-a[y].x)+a[y].x*a[z].y-a[z].x*a[y].y;
}
int main()
{
fin>>n;
for(i=1;i<=n;i++){
fin>>a[i].x>>a[i].y;
if(vy>a[i].y||vy==a[i].y&&vx>a[i].x) vx=a[i].x,vy=a[i].y;
}
for(i=1;i<=n;i++){
a[i].x-=vx,a[i].y-=vy;
if(a[i].x==0&&a[i].y==0) a[i].cad=-1,a[i].p=-1;
else{
a[i].cad=cad(a[i].x,a[i].y);
a[i].d=pow(1.0*a[i].x,2)+pow(1.0*a[i].y,2);
a[i].p=(a[i].x==0?inf:1.0*a[i].y/a[i].x);
}
}
sort(a+1,a+n+1,cmp);
s.push(1);
for(i=3;a[i].p==a[i-1].p;i++);
for(j=i-1;j>=2;j--) s.push(j);
for(;i<=n;i++){
x=s.top(),s.pop();
y=s.top();
while(det(y,x,i)<0){
x=y,s.pop(),y=s.top();
i=i;
}
s.push(x),s.push(i);
}
fout<<s.size()<<'\n';
while(!s.empty()) st.push(s.top()),s.pop();
while(!st.empty()) fout<<a[st.top()].x+vx<<' '<<a[st.top()].y+vy<<'\n', st.pop();
return 0;
}