314292026-08-29 15:08:45miszorimarciAutópálya ***cpp17Elfogadva 100/10050ms4672 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long

struct P {
    int x,y;
    int id,c;
};
P o;
int fordul(P a,P b,P c){
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}

int dist(P a){
    return (a.x-o.x)*(a.x-o.x)+(a.y-o.y)*(a.y-o.y);
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; cin>>n;
    vector<P>p;
    for(int i=1;i<=n;i++)
    {
        int x,y; cin >> x >> y;
        p.push_back({x,y,i,0});
    }

    int m; cin>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y; cin>>x>>y;
        p.push_back({x,y,i,1});
    }
    o=*min_element(p.begin(),p.end(),[](P a,P b){
        return a.y!=b.y ? a.y<b.y : a.x<b.x;
    });
    sort(p.begin(),p.end(),[](P a,P b){
        int z=fordul(o,a,b);
        if(z) return z>0;
        return dist(a)<dist(b);
    });
    vector<P> h;
    for(P x:p)
    {
        while(h.size()>=2 && fordul(h[h.size()-2],h.back(),x)<0)h.pop_back();
        h.push_back(x);
    }
    int k=h.size();
    for(int i=0;i<k;i++)
    {
        P a=h[i], b=h[(i+1)%k];
        if(a.c!=b.c)
        {
            if(a.c==0) cout<<a.id<<" "<<b.id;
            else cout<<b.id<<" "<<a.id;
            return 0;
        }
    }
    cout<<"0 0";
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base100/100
1Elfogadva2/22ms748 KiB
2Elfogadva2/22ms564 KiB
3Elfogadva2/23ms808 KiB
4Elfogadva2/22ms564 KiB
5Elfogadva2/22ms556 KiB
6Elfogadva4/44ms1012 KiB
7Elfogadva4/46ms952 KiB
8Elfogadva4/46ms948 KiB
9Elfogadva4/44ms948 KiB
10Elfogadva4/46ms948 KiB
11Elfogadva6/69ms1456 KiB
12Elfogadva6/69ms1536 KiB
13Elfogadva6/69ms1456 KiB
14Elfogadva6/610ms1484 KiB
15Elfogadva6/69ms1456 KiB
16Elfogadva8/850ms4636 KiB
17Elfogadva8/825ms2540 KiB
18Elfogadva8/850ms4516 KiB
19Elfogadva8/850ms4672 KiB
20Elfogadva8/850ms4480 KiB