TIOJ 1105 . H.PS3

convexhull + 2pointer



#include <algorithm>
#include <vector>
#include <cmath>
#include <utility>

using namespace std;

const double PI = acos(-1);
const double eps = 1e-10;

bool db_st(const double& a, const double& b){return a < b-eps;}
bool db_eq(const double& a, const double& b){return fabs(a-b)<eps;}

int sgn(double a){ return a<-eps ? -1 : a>eps;}

class pt{
public:
    double x, y;
    int id;
    pt(double _x = 0, double _y = 0):x(_x), y(_y){}
    double len()const{return sqrt(x*x + y*y);}
};

bool operator==(const pt& a, const pt& b){return sgn(a.x-b.x) == 0 and sgn(a.y-b.y) == 0;}
pt operator-(const pt& a, const pt& b){return pt(a.x - b.x, a.y - b.y);}
pt operator+(const pt& a, const pt& b){return pt(a.x + b.x, a.y + b.y);}
double operator^(const pt& a, const pt& b){return a.x*b.y - a.y*b.x;}

struct cpbyx{bool operator()(pt a, pt b){return a.x == b.x ? a.y < b.y : a.x < b.x;}};
vector<pt> ConvexHull(vector<pt> inp){
    vector<pt> bt_ret, tp_ret;
    sort(inp.begin(), inp.end(), cpbyx());
    auto it = unique(inp.begin(), inp.end());
    inp.resize(distance(inp.begin(), it));
    for(int lx = 0;lx < inp.size();lx++){
        pt v = inp[lx];
        for(int ly = (int)bt_ret.size()-1;ly>=1;ly--){
            if(sgn((bt_ret[ly]-bt_ret[ly-1])^(v-bt_ret[ly])) <= 0){
                bt_ret.pop_back();
            }else
                break;
        }
        bt_ret.push_back(v);
    }
    for(int lx = (int)inp.size()-1;lx>=0;lx--){
        pt v = inp[lx];
        for(int ly = ((int)tp_ret.size())-1;ly>=1;ly--)
            if(sgn((tp_ret[ly]-tp_ret[ly-1])^(v-tp_ret[ly])) <= 0)
                tp_ret.pop_back();
            else
                break;
        tp_ret.push_back(v);
    }
   
    vector<pt> ret;
    for(int lx = 0;lx < bt_ret.size();lx++)
        ret.push_back(bt_ret[lx]);
    for(int lx = 1;lx+1 < tp_ret.size();lx++)
        ret.push_back(tp_ret[lx]);
    return ret;
}

struct ans{ int xx, yy; ans(int _x, int _y):xx(_x), yy(_y){if(_x > _y) swap(xx, yy);}};
bool operator<(ans a1, ans a2){ return (a1.xx != a2.xx) ? a1.xx < a2.xx : a1.yy < a2.yy;}

int main(){
    int n;
    for(;;){
        scanf("%d", &n);
        if(n == 0) break;
        vector<pt> inp(n);
        for(int lx = 0;lx < n;lx++)
            scanf("%lf %lf", &inp[lx].x, &inp[lx].y), inp[lx].id = lx;
        inp = ConvexHull(inp);
        int ptr = 0;
        int sz = inp.size();
        double ll = 0, prell;
        ans aa(inp[0].id, inp[0].id);
        for(int lx = 0;lx < sz;lx++){
            prell = (inp[ptr]-inp[lx]).len();
            for(;ptr<sz;ptr++){
                ans _aa(inp[lx].id, inp[ptr].id);
                double nll = (inp[lx]-inp[ptr]).len();
                if(db_st(ll, nll) or (db_eq(ll, nll) and _aa < aa)){
                    aa = _aa;
                    ll = nll;
                }
                if(db_st(nll, prell)){
                    break;
                }
                prell = nll;
            }
            ptr--;
        }
        printf("%d %d\n", aa.xx, aa.yy);
    }
    return 0;
}