296362026-06-15 18:03:17LazurAndrasAutópálya ***cpp17Elfogadva 100/10054ms3920 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long

struct Point{
	int x, y, id;
};

int fordul(Point a, Point b, Point c)
{
	b.x -= a.x; b.y -= a.y; c.x -= a.x; c.y -= a.y;
	int s = b.x * c.y - b.y * c.x;
	return (s > 0) - (s < 0);
}

int dist(Point a, Point b, Point c)
{
	int x = (b.x-a.x) * (b.x-a.x) + (b.y-a.y) * (b.y-a.y);
	int y = (c.x-a.x) * (c.x-a.x) + (c.y-a.y) * (c.y-a.y);
	return x < y;
}

Point st;

bool srt(Point a, Point b)
{
	if(fordul(st, a, b)) return fordul(st, a, b) == 1;
	return dist(st, a, b);
}

signed main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);
	int n; cin >> n;
	vector<Point>a(n);
	for(int i = 0; i < n; i++)
	{
		cin >> a[i].x >> a[i].y;
		a[i].id = i;
	}
	int m; cin >> m;
	a.resize(n+m);
	for(int i = n; i < n+m; i++)
	{
		cin >> a[i].x >> a[i].y;
		a[i].id = i;
	}
	int mx = 0;
	for(int i = 1; i < n+m; i++)
	{
		Point u = a[i];
		if(u.y < a[mx].y || (u.y == a[mx].y && u.x < a[mx].x)) mx = i;
	}
	swap(a[0], a[mx]);
	st = a[0];
	sort(a.begin()+1, a.end(), srt);
	int x = n+m-1;
	while(!fordul(a[0], a[x-1], a.back())) x--;
	reverse(a.begin()+x, a.end());
	/*for(Point u : a) cout << u.x << " " << u.y << " " << u.id+1 << '\n';
	cout.flush();*/
	vector<Point>hull = {a[0], a[1]};
	for(int i = 2; i < n+m; i++)
	{
		while(fordul(hull[(int)hull.size()-2], hull.back(), a[i]) == -1) hull.pop_back();
		hull.push_back(a[i]);
	}
	bool ok = 1, ok2 = 1;
	for(Point u : hull)
	{
		if(u.id < n) ok = 0;
		else ok2 = 0;
	}
	if(ok || ok2) {cout << "0 0"; return 0;}
	for(int i = 1; i < (int)hull.size(); i++)
	{
		Point u = hull[i-1], v = hull[i];
		if(min(u.id, v.id) < n && max(u.id, v.id) >= n)
		{
			if(u.id > v.id) swap(u, v);
			cout << u.id+1 << " " << v.id+1-n;
			return 0;
		}
	}
	if(a[0].id > a.back().id) swap(a[0], a.back());
	cout << a[0].id+1 << " " << a.back().id+1-n;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base100/100
1Elfogadva2/22ms508 KiB
2Elfogadva2/22ms316 KiB
3Elfogadva2/22ms316 KiB
4Elfogadva2/22ms316 KiB
5Elfogadva2/22ms316 KiB
6Elfogadva4/46ms564 KiB
7Elfogadva4/46ms564 KiB
8Elfogadva4/46ms588 KiB
9Elfogadva4/46ms564 KiB
10Elfogadva4/46ms564 KiB
11Elfogadva6/69ms1076 KiB
12Elfogadva6/69ms1076 KiB
13Elfogadva6/610ms1076 KiB
14Elfogadva6/610ms932 KiB
15Elfogadva6/610ms928 KiB
16Elfogadva8/854ms3892 KiB
17Elfogadva8/828ms2616 KiB
18Elfogadva8/854ms3920 KiB
19Elfogadva8/854ms3912 KiB
20Elfogadva8/854ms3892 KiB