283812026-05-20 10:05:59LazurAndrasHáromszögekcpp17Elfogadva 100/10061ms3576 KiB
#include<bits/stdc++.h>
using namespace std;
#define int long long

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

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

bool dist(Node a, Node b, Node c)
{
    int s = (b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y);
    int z = (c.x-a.x)*(c.x-a.x)+(c.y-a.y)*(c.y-a.y);
    return s > z;
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int n; cin >> n; n -= 2;
    Node a, b; cin >> a.x >> a.y >> b.x >> b.y;
    vector<Node>p(n);
    for(int i = 0; i < n; i++)
    {
        cin >> p[i].x >> p[i].y;
        p[i].id = i;
    }
    vector<int>cnt(n, n+2);
    sort(p.begin(), p.end(), [&](Node &l, Node &r){
        if(fordul(a, l, r) == -1) return 1;
        if(fordul(a, l, r) == 0 && dist(a, l, r)) return 1;
        return 0;
        });
    for(int i = 0; i < n; i++) cnt[p[i].id] -= i;
    sort(p.begin(), p.end(), [&](Node &l, Node &r){
        if(fordul(b, l, r) == 1) return 1;
        if(fordul(b, l, r) == 0 && dist(b, l, r)) return 1;
        return 0;
        });
    for(int i = 0; i < n; i++) cnt[p[i].id] -= i;
    int ans = 0;
    for(int i = 0; i < n; i++)
    {
        if(cnt[p[i].id] > cnt[ans]) ans = p[i].id;
        else if(cnt[p[i].id] == cnt[ans] && p[i].id < ans) ans = p[i].id;
    }
    cout << ans+3 << " " << cnt[ans];
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms316 KiB
2Elfogadva37ms2100 KiB
subtask25/5
3Elfogadva2ms500 KiB
4Elfogadva2ms316 KiB
5Elfogadva2ms508 KiB
6Elfogadva2ms316 KiB
7Elfogadva1ms316 KiB
8Elfogadva1ms316 KiB
subtask310/10
9Elfogadva1ms316 KiB
10Elfogadva1ms508 KiB
11Elfogadva3ms488 KiB
12Elfogadva25ms1592 KiB
13Elfogadva30ms1864 KiB
14Elfogadva1ms316 KiB
subtask410/10
15Elfogadva2ms316 KiB
16Elfogadva2ms316 KiB
17Elfogadva2ms384 KiB
18Elfogadva2ms316 KiB
19Elfogadva2ms316 KiB
20Elfogadva2ms316 KiB
21Elfogadva12ms1144 KiB
22Elfogadva10ms1140 KiB
23Elfogadva10ms1152 KiB
24Elfogadva39ms3568 KiB
subtask520/20
25Elfogadva2ms500 KiB
26Elfogadva2ms316 KiB
27Elfogadva2ms508 KiB
28Elfogadva2ms316 KiB
29Elfogadva1ms316 KiB
30Elfogadva1ms316 KiB
31Elfogadva1ms316 KiB
32Elfogadva1ms508 KiB
33Elfogadva3ms488 KiB
34Elfogadva25ms1592 KiB
35Elfogadva30ms1864 KiB
36Elfogadva2ms316 KiB
37Elfogadva3ms316 KiB
38Elfogadva3ms316 KiB
39Elfogadva3ms316 KiB
40Elfogadva3ms564 KiB
41Elfogadva6ms564 KiB
42Elfogadva12ms1068 KiB
43Elfogadva17ms1372 KiB
44Elfogadva24ms1588 KiB
45Elfogadva29ms1868 KiB
46Elfogadva28ms2032 KiB
47Elfogadva1ms316 KiB
subtask655/55
48Elfogadva2ms500 KiB
49Elfogadva37ms2100 KiB
50Elfogadva2ms316 KiB
51Elfogadva2ms508 KiB
52Elfogadva2ms316 KiB
53Elfogadva1ms316 KiB
54Elfogadva1ms316 KiB
55Elfogadva1ms316 KiB
56Elfogadva1ms508 KiB
57Elfogadva3ms488 KiB
58Elfogadva25ms1592 KiB
59Elfogadva30ms1864 KiB
60Elfogadva2ms316 KiB
61Elfogadva2ms316 KiB
62Elfogadva2ms384 KiB
63Elfogadva2ms316 KiB
64Elfogadva2ms316 KiB
65Elfogadva2ms316 KiB
66Elfogadva12ms1144 KiB
67Elfogadva10ms1140 KiB
68Elfogadva10ms1152 KiB
69Elfogadva39ms3568 KiB
70Elfogadva2ms316 KiB
71Elfogadva3ms316 KiB
72Elfogadva3ms316 KiB
73Elfogadva3ms316 KiB
74Elfogadva3ms564 KiB
75Elfogadva6ms564 KiB
76Elfogadva12ms1068 KiB
77Elfogadva17ms1372 KiB
78Elfogadva24ms1588 KiB
79Elfogadva29ms1868 KiB
80Elfogadva2ms508 KiB
81Elfogadva3ms316 KiB
82Elfogadva3ms316 KiB
83Elfogadva3ms368 KiB
84Elfogadva3ms564 KiB
85Elfogadva6ms568 KiB
86Elfogadva12ms820 KiB
87Elfogadva17ms1380 KiB
88Elfogadva24ms1588 KiB
89Elfogadva29ms1844 KiB
90Elfogadva35ms2100 KiB
91Elfogadva43ms2632 KiB
92Elfogadva48ms2832 KiB
93Elfogadva56ms3124 KiB
94Elfogadva56ms3124 KiB
95Elfogadva61ms3556 KiB
96Elfogadva61ms3576 KiB
97Elfogadva57ms3568 KiB
98Elfogadva56ms3568 KiB
99Elfogadva61ms3564 KiB
100Elfogadva28ms2032 KiB
101Elfogadva1ms316 KiB