QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#364073 | #2838. 2D Geometry | x_jw# | WA | 2ms | 3852kb | C++14 | 1.1kb | 2024-03-24 11:19:12 | 2024-03-24 11:19:13 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using db=double;
#define int long long
using pii=pair<int,int>;
#define endl "\n"
#define pb push_back
void solve(int n)
{
vector<pii>pic;
for(int i=0;i<n;i++)
{
int x,y;
cin>>x>>y;
pic.pb({x,y});
}
if(n<3)
{
cout<<n<<endl;
return;
}
int k = 2e3,ma = 0;
while(k--){
int p1 = rand()%n,p2 = rand()%n;
while(p2 == p1)p2 = rand()%n;
int x1=pic[p1].first-pic[p2].first;
int y1=pic[p1].second-pic[p2].second;
int res = 2;
for(int i=0;i<n;i++)
{
if(i == p1||i == p2)continue;
int x=pic[i].first-pic[p1].first;
int y=pic[i].second-pic[p1].second;
if(1ll*x*y1==1ll*y*x1)res++;
}
ma = max(ma,res);
}
int cn = min(ma/2,n-ma);
cout<<n-cn*3<<endl;
}
signed main()
{
#ifdef ONLINE_JUDGE
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
#endif
int _=1;
while(cin>>_) solve(_);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3576kb
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
Wrong Answer
time: 2ms
memory: 3852kb
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:
1 2 3 0 1 1 4 2 2 2 2 5 3 3 0 3 3 0 3 3 3 6
result:
wrong answer 13th lines differ - expected: '0', found: '3'