QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#63277#2838. 2D Geometrykasiruto#TL 2ms3240kbC++17959b2022-11-21 13:36:152022-11-21 13:36:17

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-21 13:36:17]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:3240kb
  • [2022-11-21 13:36:15]
  • 提交

answer

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using i64=long long;
using pll=pair<i64,i64>;
int n;
void work(){
    vector<pll>p(n+1);
    for (int i=1;i<=n;i++){
        cin>>p[i].fi>>p[i].se;
    }
    int ma=0;
    for (int i=1;i<=100;i++){
        int x,y,nu=2;
        x=rand()%n+1;
        y=rand()%n+1;
        while (y==x) y=rand()%n+1;
        pll l1={p[x].fi-p[y].fi,p[x].se-p[y].se},l2;
        for (int j=1;j<=n;j++){
            if (j==x||j==y) continue;
            l2={p[j].fi-p[y].fi,p[j].se-p[y].se};
            if (l1.fi*l2.se-l1.se*l2.fi==0)
                nu++;
        }
        ma=max(nu,ma);
    }
    if (ma<=n*2/3)
        cout<<n%3<<'\n';
    else cout<<ma-(n-ma)*2<<'\n';
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    #ifdef LC
    freopen("t.in","r",stdin);
    freopen("t.out","w",stdout);
    #endif
    while (cin>>n)
        work();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3240kb

input:

3
0 0
0 1
0 2
3
0 0
0 1
1 0
6
0 0
0 1
0 2
0 3
1 1
1 2

output:

3
0
0

result:

ok 3 lines

Test #2:

score: -100
Time Limit Exceeded

input:

1
0 0
2
0 0
1 1
3
0 0
0 1
0 2
3
0 0
0 1
1 0
4
3 0
0 2
3 3
3 1
4
2 3
1 1
0 3
0 2
4
0 0
0 3
0 2
0 1
5
8 6
9 2
2 3
7 4
1 5
5
2 2
4 2
6 2
7 2
0 4
5
3 7
5 4
4 4
9 4
9 9
5
5 4
5 9
5 5
4 3
1 0
5
3 2
1 2
7 2
6 2
5 2
6
7 2
7 9
0 3
8 8
4 4
3 8
6
2 8
2 5
3 5
3 8
2 0
0 2
6
2 3
8 4
2 9
2 2
2 6
4 9
6
2 1
7 6
6 5
...

output:


result: