| 28227 | 2026-05-18 10:24:38 | PappMatyas | Háromszögek | cpp17 | Elfogadva 100/100 | 115ms | 7156 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 | Összpont | Teszt | Verdikt | Idő | Memória | ||
|---|---|---|---|---|---|---|---|
| subtask1 | 0/0 | ||||||
| 1 | Elfogadva | 1ms | 508 KiB | ||||
| 2 | Elfogadva | 68ms | 4408 KiB | ||||
| subtask2 | 5/5 | ||||||
| 3 | Elfogadva | 2ms | 316 KiB | ||||
| 4 | Elfogadva | 2ms | 540 KiB | ||||
| 5 | Elfogadva | 2ms | 316 KiB | ||||
| 6 | Elfogadva | 2ms | 316 KiB | ||||
| 7 | Elfogadva | 1ms | 316 KiB | ||||
| 8 | Elfogadva | 1ms | 316 KiB | ||||
| subtask3 | 10/10 | ||||||
| 9 | Elfogadva | 1ms | 316 KiB | ||||
| 10 | Elfogadva | 2ms | 316 KiB | ||||
| 11 | Elfogadva | 4ms | 564 KiB | ||||
| 12 | Elfogadva | 46ms | 3064 KiB | ||||
| 13 | Elfogadva | 57ms | 3740 KiB | ||||
| 14 | Elfogadva | 1ms | 316 KiB | ||||
| subtask4 | 10/10 | ||||||
| 15 | Elfogadva | 2ms | 512 KiB | ||||
| 16 | Elfogadva | 2ms | 316 KiB | ||||
| 17 | Elfogadva | 2ms | 508 KiB | ||||
| 18 | Elfogadva | 1ms | 316 KiB | ||||
| 19 | Elfogadva | 3ms | 568 KiB | ||||
| 20 | Elfogadva | 3ms | 564 KiB | ||||
| 21 | Elfogadva | 27ms | 2228 KiB | ||||
| 22 | Elfogadva | 25ms | 2412 KiB | ||||
| 23 | Elfogadva | 25ms | 2356 KiB | ||||
| 24 | Elfogadva | 85ms | 6964 KiB | ||||
| subtask5 | 20/20 | ||||||
| 25 | Elfogadva | 2ms | 316 KiB | ||||
| 26 | Elfogadva | 2ms | 540 KiB | ||||
| 27 | Elfogadva | 2ms | 316 KiB | ||||
| 28 | Elfogadva | 2ms | 316 KiB | ||||
| 29 | Elfogadva | 1ms | 316 KiB | ||||
| 30 | Elfogadva | 1ms | 316 KiB | ||||
| 31 | Elfogadva | 1ms | 316 KiB | ||||
| 32 | Elfogadva | 2ms | 316 KiB | ||||
| 33 | Elfogadva | 4ms | 564 KiB | ||||
| 34 | Elfogadva | 46ms | 3064 KiB | ||||
| 35 | Elfogadva | 57ms | 3740 KiB | ||||
| 36 | Elfogadva | 2ms | 464 KiB | ||||
| 37 | Elfogadva | 3ms | 508 KiB | ||||
| 38 | Elfogadva | 4ms | 564 KiB | ||||
| 39 | Elfogadva | 4ms | 664 KiB | ||||
| 40 | Elfogadva | 6ms | 564 KiB | ||||
| 41 | Elfogadva | 9ms | 1076 KiB | ||||
| 42 | Elfogadva | 23ms | 1744 KiB | ||||
| 43 | Elfogadva | 32ms | 2408 KiB | ||||
| 44 | Elfogadva | 43ms | 3084 KiB | ||||
| 45 | Elfogadva | 57ms | 3736 KiB | ||||
| 46 | Elfogadva | 43ms | 3636 KiB | ||||
| 47 | Elfogadva | 1ms | 316 KiB | ||||
| subtask6 | 55/55 | ||||||
| 48 | Elfogadva | 2ms | 316 KiB | ||||
| 49 | Elfogadva | 71ms | 4404 KiB | ||||
| 50 | Elfogadva | 2ms | 540 KiB | ||||
| 51 | Elfogadva | 2ms | 316 KiB | ||||
| 52 | Elfogadva | 2ms | 316 KiB | ||||
| 53 | Elfogadva | 1ms | 316 KiB | ||||
| 54 | Elfogadva | 1ms | 316 KiB | ||||
| 55 | Elfogadva | 1ms | 316 KiB | ||||
| 56 | Elfogadva | 2ms | 316 KiB | ||||
| 57 | Elfogadva | 4ms | 564 KiB | ||||
| 58 | Elfogadva | 46ms | 3064 KiB | ||||
| 59 | Elfogadva | 57ms | 3740 KiB | ||||
| 60 | Elfogadva | 2ms | 512 KiB | ||||
| 61 | Elfogadva | 2ms | 316 KiB | ||||
| 62 | Elfogadva | 2ms | 508 KiB | ||||
| 63 | Elfogadva | 1ms | 316 KiB | ||||
| 64 | Elfogadva | 3ms | 568 KiB | ||||
| 65 | Elfogadva | 3ms | 564 KiB | ||||
| 66 | Elfogadva | 27ms | 2228 KiB | ||||
| 67 | Elfogadva | 25ms | 2412 KiB | ||||
| 68 | Elfogadva | 25ms | 2356 KiB | ||||
| 69 | Elfogadva | 85ms | 6964 KiB | ||||
| 70 | Elfogadva | 2ms | 464 KiB | ||||
| 71 | Elfogadva | 3ms | 508 KiB | ||||
| 72 | Elfogadva | 4ms | 564 KiB | ||||
| 73 | Elfogadva | 4ms | 664 KiB | ||||
| 74 | Elfogadva | 6ms | 564 KiB | ||||
| 75 | Elfogadva | 9ms | 1076 KiB | ||||
| 76 | Elfogadva | 23ms | 1744 KiB | ||||
| 77 | Elfogadva | 32ms | 2408 KiB | ||||
| 78 | Elfogadva | 43ms | 3084 KiB | ||||
| 79 | Elfogadva | 57ms | 3736 KiB | ||||
| 80 | Elfogadva | 3ms | 508 KiB | ||||
| 81 | Elfogadva | 4ms | 500 KiB | ||||
| 82 | Elfogadva | 4ms | 564 KiB | ||||
| 83 | Elfogadva | 4ms | 564 KiB | ||||
| 84 | Elfogadva | 6ms | 648 KiB | ||||
| 85 | Elfogadva | 10ms | 1052 KiB | ||||
| 86 | Elfogadva | 21ms | 1588 KiB | ||||
| 87 | Elfogadva | 32ms | 2220 KiB | ||||
| 88 | Elfogadva | 45ms | 2876 KiB | ||||
| 89 | Elfogadva | 57ms | 3636 KiB | ||||
| 90 | Elfogadva | 67ms | 4408 KiB | ||||
| 91 | Elfogadva | 85ms | 4916 KiB | ||||
| 92 | Elfogadva | 90ms | 5736 KiB | ||||
| 93 | Elfogadva | 104ms | 6212 KiB | ||||
| 94 | Elfogadva | 108ms | 6196 KiB | ||||
| 95 | Elfogadva | 115ms | 7068 KiB | ||||
| 96 | Elfogadva | 115ms | 6964 KiB | ||||
| 97 | Elfogadva | 115ms | 6964 KiB | ||||
| 98 | Elfogadva | 114ms | 6964 KiB | ||||
| 99 | Elfogadva | 115ms | 7156 KiB | ||||
| 100 | Elfogadva | 43ms | 3636 KiB | ||||
| 101 | Elfogadva | 1ms | 316 KiB | ||||