Cod sursa(job #3335973)

Utilizator GliggyGligor Andrei Gliggy Data 23 ianuarie 2026 22:12:04
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.11 kb
// // 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);
//     s.push(2);
//     for(i=3;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<<fixed<<setprecision(6)<<a[st.top()].x+vx<<' '<<a[st.top()].y+vy<<'\n', st.pop();
//     return 0;
// }
#include <bits/stdc++.h>

using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
long long n,i,j,top;
double vx=2e9,vy=2e9;
struct pct{
    double x,y;
};
pct a[120010],st[120010],p0;
double det(pct p1,pct p2,pct p3){
    return (p2.x-p1.x)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x);
}
double dist(pct p1,pct p2){
    return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);
}
bool cmp(pct b,pct c){
    double d=det(p0,b,c);
    if(abs(d)<1e-9) return dist(p0,b)<dist(p0,c);
    return d>0;
}
int main(){
    if(!(fin>>n)) return 0;
    for(i=1;i<=n;i++){
        fin>>a[i].x>>a[i].y;
        if(a[i].y<vy||(a[i].y==vy&&a[i].x<vx)) vx=a[i].x,vy=a[i].y;
    }
    p0={vx,vy};
    sort(a+1,a+n+1,cmp);
    st[++top]=a[1];
    for(i=2;i<=n;i++){
        while(top>=2&&det(st[top-1],st[top],a[i])<=1e-11) top--;
        st[++top]=a[i];
    }
    fout<<top<<'\n';
    fout<<fixed<<setprecision(6);
    for(i=1;i<=top;i++) fout<<st[i].x<<' '<<st[i].y<<'\n';
    return 0;
}