266412026-04-05 10:05:34KristófHáromszögekcpp17Elfogadva 100/10067ms5920 KiB
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Point
{
long long x,y;
int id;
bool operator==(const Point &other)
    {
    return x==other.x && y==other.y;
    }
};

int fordul(Point &a,Point &b,Point &c)
{
long long s=(c.y-a.y)*(b.x-a.x)-(c.x-a.x)*(b.y-a.y);
return (s>0)-(s<0);
}
long long pitagorasz(Point &a,Point &b)
{
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;cin>>n;
    vector<Point> pontok1(n);
    vector<Point> pontok2(n);
    for(int i=0;i<n;i++)
        {
        cin>>pontok1[i].x>>pontok1[i].y;
        pontok1[i].id=i;
        }
    pontok2=pontok1;
    sort(pontok1.begin()+2,pontok1.end(),[&](Point a,Point b)
         {
         if(fordul(pontok1[0],a,b)==0)
            {
            return pitagorasz(pontok1[0],a)>pitagorasz(pontok1[0],b);
            }
         return fordul(pontok1[0],a,b)<0;
         });
    //swap(pontok2[1],pontok2[0]);
    //cout<<pontok2[0].x<<" "<<pontok2[0].y<<"\n\n";
    sort(pontok2.begin()+2,pontok2.end(),[&](Point a,Point b)
         {
         if(fordul(pontok2[1],a,b)==0)
            {
            return pitagorasz(pontok2[1],a)>pitagorasz(pontok2[1],b);
            }
         return fordul(pontok2[1],  a,b)>0;
         });
    //for(int i=0;i<n;i++)cout<<pontok2[i].x<<" "<<pontok2[i].y<<"\n";
    //cout<<"\n\n\n";
    //for(int i=0;i<n;i++)cout<<pontok1[i].x<<" "<<pontok1[i].y<<"\n";
    pair<int,int> ans;
    vector<int> indexinp2(n),indexinp1(n);
    for (int i=2;i<pontok2.size();i++) {
        indexinp2[pontok2[i].id]=i;
        indexinp1[pontok1[i].id]=i;
    }
    ans.first=0;
    for(int id=2;id<n;id++)
        {
        int curr=n-indexinp1[id]-indexinp2[id]+4;
        //cout<<curr<<" "<<i<<"\n";
        if(curr>ans.first)
            {
            ans.first=curr;
            ans.second=id;
            }
        }
    cout<<ans.second+1<<" "<<ans.first;
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms500 KiB
2Elfogadva39ms3636 KiB
subtask25/5
3Elfogadva2ms316 KiB
4Elfogadva2ms316 KiB
5Elfogadva2ms316 KiB
6Elfogadva1ms508 KiB
7Elfogadva1ms316 KiB
8Elfogadva1ms316 KiB
subtask310/10
9Elfogadva1ms316 KiB
10Elfogadva1ms316 KiB
11Elfogadva3ms564 KiB
12Elfogadva26ms2592 KiB
13Elfogadva32ms3044 KiB
14Elfogadva1ms316 KiB
subtask410/10
15Elfogadva2ms316 KiB
16Elfogadva2ms508 KiB
17Elfogadva2ms316 KiB
18Elfogadva2ms316 KiB
19Elfogadva2ms564 KiB
20Elfogadva2ms564 KiB
21Elfogadva13ms1844 KiB
22Elfogadva12ms1848 KiB
23Elfogadva10ms1852 KiB
24Elfogadva39ms5892 KiB
subtask520/20
25Elfogadva2ms316 KiB
26Elfogadva2ms316 KiB
27Elfogadva2ms316 KiB
28Elfogadva1ms508 KiB
29Elfogadva1ms316 KiB
30Elfogadva1ms316 KiB
31Elfogadva1ms316 KiB
32Elfogadva1ms316 KiB
33Elfogadva3ms564 KiB
34Elfogadva26ms2592 KiB
35Elfogadva32ms3044 KiB
36Elfogadva2ms512 KiB
37Elfogadva3ms316 KiB
38Elfogadva3ms756 KiB
39Elfogadva3ms564 KiB
40Elfogadva4ms440 KiB
41Elfogadva6ms820 KiB
42Elfogadva13ms1320 KiB
43Elfogadva18ms1844 KiB
44Elfogadva25ms2568 KiB
45Elfogadva30ms3040 KiB
46Elfogadva30ms3124 KiB
47Elfogadva1ms316 KiB
subtask655/55
48Elfogadva2ms316 KiB
49Elfogadva39ms3516 KiB
50Elfogadva2ms316 KiB
51Elfogadva2ms316 KiB
52Elfogadva1ms508 KiB
53Elfogadva1ms316 KiB
54Elfogadva1ms316 KiB
55Elfogadva1ms316 KiB
56Elfogadva1ms316 KiB
57Elfogadva3ms564 KiB
58Elfogadva26ms2592 KiB
59Elfogadva32ms3044 KiB
60Elfogadva2ms316 KiB
61Elfogadva2ms508 KiB
62Elfogadva2ms316 KiB
63Elfogadva2ms316 KiB
64Elfogadva2ms564 KiB
65Elfogadva2ms564 KiB
66Elfogadva13ms1844 KiB
67Elfogadva12ms1848 KiB
68Elfogadva10ms1852 KiB
69Elfogadva39ms5892 KiB
70Elfogadva2ms512 KiB
71Elfogadva3ms316 KiB
72Elfogadva3ms756 KiB
73Elfogadva3ms564 KiB
74Elfogadva4ms440 KiB
75Elfogadva6ms820 KiB
76Elfogadva13ms1320 KiB
77Elfogadva18ms1844 KiB
78Elfogadva25ms2568 KiB
79Elfogadva30ms3040 KiB
80Elfogadva1ms316 KiB
81Elfogadva2ms316 KiB
82Elfogadva3ms568 KiB
83Elfogadva3ms564 KiB
84Elfogadva3ms568 KiB
85Elfogadva6ms820 KiB
86Elfogadva13ms1380 KiB
87Elfogadva18ms1860 KiB
88Elfogadva26ms2568 KiB
89Elfogadva32ms3124 KiB
90Elfogadva37ms3508 KiB
91Elfogadva46ms4248 KiB
92Elfogadva52ms4712 KiB
93Elfogadva61ms5172 KiB
94Elfogadva59ms5184 KiB
95Elfogadva65ms5680 KiB
96Elfogadva65ms5684 KiB
97Elfogadva67ms5896 KiB
98Elfogadva65ms5904 KiB
99Elfogadva65ms5920 KiB
100Elfogadva30ms3124 KiB
101Elfogadva1ms316 KiB