QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#102622 | #3189. Finding Lines | PetroTarnavskyi# | TL | 2ms | 3464kb | C++17 | 1.2kb | 2023-05-03 15:13:42 | 2023-05-03 15:14:01 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define MP make_pair
#define PB push_back
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
struct point
{
LL x, y;
point(): x(0), y(0) {}
point(LL _x, LL _y): x(_x), y(_y) {}
point operator -(const point p) const
{
return point(x - p.x, y - p.y);
}
long long operator *(const point p) const
{
return x * p.y - y * p.x;
}
};
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
srand(47);
int n, p;
cin >> n >> p;
if (n < 3)
{
cout << "possible\n";
return 0;
}
vector<point> v(n);
FOR(i, 0, n) cin >> v[i].x >> v[i].y;
while(double(clock()) / CLOCKS_PER_SEC < 3.74)
{
int i = rand() % n;
int j = rand() % n;
if (i == j) continue;
int cnt = 0;
FOR(k, 0, n)
{
if ((v[k] - v[i]) * (v[j] - v[i]) == 0)
cnt++;
}
// cnt / n >= p /100
if (100 * cnt >= n * p)
{
cout << "possible\n";
return 0;
}
}
cout << "impossible\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3464kb
input:
5 55 0 0 10 10 10 0 0 10 3 3
output:
possible
result:
ok single line: 'possible'
Test #2:
score: -100
Time Limit Exceeded
input:
5 45 0 0 10 10 10 0 0 10 3 4