282272026-05-18 10:24:38PappMatyasHáromszögekcpp17Elfogadva 100/100115ms7156 KiB
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
using ll = long long;

struct int2
{
	ll x;
	ll y;
};

struct func
{
	ll x;
	ll y;
	int ind;
};

int2 a;
int2 b;
vector<int2> points;
vector<func> aFunc;
vector<func> bFunc;
vector<int> sub;

static bool CompareA(func p, func q)
{
	return p.x * q.y < p.y * q.x;
}

static bool CompareB(func p, func q)
{
	return p.y * q.x < p.x * q.y;
}

int main()
{
	ll n;
	cin >> n;
	cin >> a.x >> a.y;
	cin >> b.x >> b.y;
	n -= 2;

	points.resize(n);
	aFunc.resize(n);
	bFunc.resize(n);
	sub.resize(n, 0);
	for (int i = 0; i < n; i++)
	{
		cin >> points[i].x >> points[i].y;

		aFunc[i].x = (points[i].x - a.x);
		bFunc[i].x = (points[i].x - b.x);

		aFunc[i].y = (points[i].y - a.y);
		bFunc[i].y = (points[i].y - b.y);

		aFunc[i].ind = i;
		bFunc[i].ind = i;
	}
	/*
	cout << endl;
	for (int i = 0; i < n; i++)
	{
	    cout << aFunc[i].first << " " << aFunc[i].second;
		cout << endl;
	}

	cout << endl;
	for (int i = 0; i < n; i++)
	{
		cout << bFunc[i].first << " " << bFunc[i].second;
		cout << endl;
	}
	*/

	sort(aFunc.begin(), aFunc.end(), CompareA);
	sort(bFunc.begin(), bFunc.end(), CompareB);

	/*
	cout << endl;
	for (int i = 0; i < n; i++)
	{
		cout << aFunc[i].first << " " << aFunc[i].second + 3;
		cout << endl;
	}

	cout << endl;
	for (int i = 0; i < n; i++)
	{
		cout << bFunc[i].first << " " << bFunc[i].second + 3;
		cout << endl;
	}
	*/

	int eqa = 0;
	int eqb = 0;
	for (int i = 0; i < n; i++)
	{
		if (i > 0) if (aFunc[i].x * aFunc[i - 1].y == aFunc[i].y * aFunc[i - 1].x) eqa++;
		else eqa = 0;
		sub[aFunc[i].ind] += i - eqa;
		if (i > 0) if (bFunc[i].x * bFunc[i - 1].y == bFunc[i].y * bFunc[i - 1].x) eqb++;
		else eqb = 0;
		sub[bFunc[i].ind] += i - eqb;
	}
	/*
	cout << endl;
	for (int i = 0; i < n; i++)
	{
		cout << i + 3 << ": " << sub[i] << "\n";
	}
	cout << endl;
	*/
	int maxim = -1;
	int save = -1;
	for (int i = 0; i < n; i++)
	{
		if (n - sub[i] + 2 > maxim)
		{
			maxim = n - sub[i] + 2;
			save = i + 3;
		}
	}

	cout << save << " " << maxim;
	return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms508 KiB
2Elfogadva68ms4408 KiB
subtask25/5
3Elfogadva2ms316 KiB
4Elfogadva2ms540 KiB
5Elfogadva2ms316 KiB
6Elfogadva2ms316 KiB
7Elfogadva1ms316 KiB
8Elfogadva1ms316 KiB
subtask310/10
9Elfogadva1ms316 KiB
10Elfogadva2ms316 KiB
11Elfogadva4ms564 KiB
12Elfogadva46ms3064 KiB
13Elfogadva57ms3740 KiB
14Elfogadva1ms316 KiB
subtask410/10
15Elfogadva2ms512 KiB
16Elfogadva2ms316 KiB
17Elfogadva2ms508 KiB
18Elfogadva1ms316 KiB
19Elfogadva3ms568 KiB
20Elfogadva3ms564 KiB
21Elfogadva27ms2228 KiB
22Elfogadva25ms2412 KiB
23Elfogadva25ms2356 KiB
24Elfogadva85ms6964 KiB
subtask520/20
25Elfogadva2ms316 KiB
26Elfogadva2ms540 KiB
27Elfogadva2ms316 KiB
28Elfogadva2ms316 KiB
29Elfogadva1ms316 KiB
30Elfogadva1ms316 KiB
31Elfogadva1ms316 KiB
32Elfogadva2ms316 KiB
33Elfogadva4ms564 KiB
34Elfogadva46ms3064 KiB
35Elfogadva57ms3740 KiB
36Elfogadva2ms464 KiB
37Elfogadva3ms508 KiB
38Elfogadva4ms564 KiB
39Elfogadva4ms664 KiB
40Elfogadva6ms564 KiB
41Elfogadva9ms1076 KiB
42Elfogadva23ms1744 KiB
43Elfogadva32ms2408 KiB
44Elfogadva43ms3084 KiB
45Elfogadva57ms3736 KiB
46Elfogadva43ms3636 KiB
47Elfogadva1ms316 KiB
subtask655/55
48Elfogadva2ms316 KiB
49Elfogadva71ms4404 KiB
50Elfogadva2ms540 KiB
51Elfogadva2ms316 KiB
52Elfogadva2ms316 KiB
53Elfogadva1ms316 KiB
54Elfogadva1ms316 KiB
55Elfogadva1ms316 KiB
56Elfogadva2ms316 KiB
57Elfogadva4ms564 KiB
58Elfogadva46ms3064 KiB
59Elfogadva57ms3740 KiB
60Elfogadva2ms512 KiB
61Elfogadva2ms316 KiB
62Elfogadva2ms508 KiB
63Elfogadva1ms316 KiB
64Elfogadva3ms568 KiB
65Elfogadva3ms564 KiB
66Elfogadva27ms2228 KiB
67Elfogadva25ms2412 KiB
68Elfogadva25ms2356 KiB
69Elfogadva85ms6964 KiB
70Elfogadva2ms464 KiB
71Elfogadva3ms508 KiB
72Elfogadva4ms564 KiB
73Elfogadva4ms664 KiB
74Elfogadva6ms564 KiB
75Elfogadva9ms1076 KiB
76Elfogadva23ms1744 KiB
77Elfogadva32ms2408 KiB
78Elfogadva43ms3084 KiB
79Elfogadva57ms3736 KiB
80Elfogadva3ms508 KiB
81Elfogadva4ms500 KiB
82Elfogadva4ms564 KiB
83Elfogadva4ms564 KiB
84Elfogadva6ms648 KiB
85Elfogadva10ms1052 KiB
86Elfogadva21ms1588 KiB
87Elfogadva32ms2220 KiB
88Elfogadva45ms2876 KiB
89Elfogadva57ms3636 KiB
90Elfogadva67ms4408 KiB
91Elfogadva85ms4916 KiB
92Elfogadva90ms5736 KiB
93Elfogadva104ms6212 KiB
94Elfogadva108ms6196 KiB
95Elfogadva115ms7068 KiB
96Elfogadva115ms6964 KiB
97Elfogadva115ms6964 KiB
98Elfogadva114ms6964 KiB
99Elfogadva115ms7156 KiB
100Elfogadva43ms3636 KiB
101Elfogadva1ms316 KiB