QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#107995 | #2838. 2D Geometry | l1924365846 | WA | 8ms | 3824kb | C++17 | 2.8kb | 2023-05-23 13:25:38 | 2023-05-23 13:25:40 |
Judging History
answer
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <set>
#include <unordered_map>
#include <unordered_set>
#define ll long long
#define int ll
#define ms(a,b) memset((a),(b),sizeof(a))
#define mc(a,b) memcpy((a),(b),sizeof(a))
#define PI acos(-1)
#define ssin(x) sin(x*PI/180.00)
#define ccos(x) cos(x*PI/180.00)
#define ttan(X) tan(x*PI/180.00)
#define rep(i, a, n) for (int i = a; i < n; i++)
#define per(i, n, a) for (int i = n - 1; i >= a; i--)
#define IOS ios::sync_with_stdio(false)
#define si(x) scanf("%d",&x)
#define sii(x, y) scanf("%d %d",&x, &y)
#define siii(x, y, z) scanf("%d %d %d",&x, &y, &z)
#define siiii(x, y, z, w) scanf("%d %d %d %d",&x, &y, &z, &w)
#define sl(x) scanf("%lld",&x)
#define sll(x, y) scanf("%lld %lld",&x, &y)
#define slll(x, y, z) scanf("%lld %lld %lld",&x, &y, &z)
#define sllll(x, y, z, w) scanf("%lld %lld %lld %lld",&x, &y, &z, &w)
#define pr(x) printf("%d",x)
#define pl(x) printf("%lld",x)
#define sd(x) scanf("%lf",&x)
#define sdd(x, y) scanf("%lf %lf",&x, &y)
#define sddd(x, y, z) scanf("%lf %lf %lf",&x, &y, &z)
#define sdddd(x, y, z, w) scanf("%lf %lf %lf %lf",&x, &y, &z, &w)
#define fi first
#define se second
#define pb push_back
#define mk make_mair
using namespace std;
typedef unsigned long long ull;
typedef pair<int, int> PII;
const int mod = 1e9 + 7;
const int P = 131;
const int N = 2e5 + 10, M = 3e6 + 10;
const int inf = 0x3f3f3f3f;
const ll lnf = 9e18;
const double eps = 1e-6;
int n;
struct F {
int x, y;
} f[N];
map<int, int> ma;
map<int, int> mb;
map<PII, int> mp;
int check (int a, int b) {
int x = f[a].x, y = f[a].y, xx = f[b].x, yy = f[b].y;
int cnt = 2;
for (int i = 0; i < n; i ++) {
if (i != a && i != b) {
int xxx = f[i].x, yyy = f[i].y;
if ( (xxx - xx) * (y - yy) == (yyy - yy) * (x - xx) ) {
cnt++;
}
}
}
return cnt;
}
void solve() {
srand ( (unsigned) time (NULL) );
while (~scanf ("%lld", &n) ) {
ma.clear(), mb.clear();
mp.clear();
int kk = 0;
for (int i = 0; i < n; i ++) {
int x, y;
sll (x, y);
f[i] = {x, y};
ma[x]++;
mb[y]++;
kk = max (kk, max (ma[x], mb[y]) );
}
for (int i = 0; i < 5000; i ++) {
int x = rand() % n, y = rand() % n;
if (x == y || mp[ {x, y}] == 1)
continue;
mp[ {x, y}] = 1;
kk = max (kk, check (x, y) );
}
if (kk <= (n - kk) * 2) {
puts ("0");
}
else {
printf ("%lld\n", kk - 2 * (n - kk) );
}
}
}
signed main() {
// IOS;
// cin.tie (0);
// cout.tie (0);
int T (1);
// sl (T);
while ( T-- ) {
solve();
}
return 0;
}
/*
4
0 0
0 1
0 2
1 1
3
0 0
0 1
1 0
6
0 0
0 1
0 2
0 3
1 1
1 2
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3824kb
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: 8ms
memory: 3660kb
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 0 4 0 2 0 0 5 0 0 0 0 0 0 0 3 0 6
result:
wrong answer 6th lines differ - expected: '1', found: '0'