QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#21780 | #2838. 2D Geometry | ha114514ha# | TL | 353ms | 11508kb | C++20 | 2.9kb | 2022-03-08 15:20:16 | 2022-05-08 04:03:46 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string.h>
#include<queue>
#include<vector>
#include<map>
#include<bitset>
#include<set>
#include<cmath>
#include<ctime>
#include<random>
#define vi vector<int>
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define bc(x) __builtin_popcount(x)
#define re register
#define il inline
#define pii pair<int,int>
#define pil pair<int,long long>
#define pll pair<long long,long long>
#define mem0(x) memset(x,0,sizeof(x))
#define mem0x3f(x) memset(x,0x3f,sizeof(x))
#define dbg(x) cerr<<"In Line "<< __LINE__<<" the "<<#x<<" = "<<x<<'\n';
// #pragma GCC optimize(3)
#define int long long
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
namespace IO_BUFF{
mt19937 rnd(time(0)^(ll)(new char));
int rend(int x){
return rnd()%x+1;
}
void rendom_shuffle(int *a,int len){
shuffle(a+1,a+len+1,rnd);
}
const int BS=(1<<24)+5;char Buffer[BS],*HD,*TL;
inline int gc(){
if(HD==TL) TL=(HD=Buffer)+fread(Buffer,1,BS,stdin);
return (HD==TL)?EOF:*HD++;
}
inline int inn(){
int x,ch,s=1;while((ch=gc())<'0'||ch>'9')if(ch=='-')s=-1;x=ch^'0';
while((ch=gc())>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^'0');return x*s;
}
char ssss[19999999],tttt[20];int ssl,ttl;
inline int print(int x)
{
if(x<0)ssss[++ssl]='-',x=(-x);
if(!x) ssss[++ssl]='0';for(ttl=0;x;x/=10) tttt[++ttl]=char(x%10+'0');
for(;ttl;ttl--) ssss[++ssl]=tttt[ttl];return ssss[++ssl]='\n';
}
inline int Flush(){return fwrite(ssss+1,sizeof(char),ssl,stdout),ssl=0,0;}
int read(){
char c=getchar();int x=1;int s=0;
while(c<'0' || c>'9'){if(c=='-')x=-1;c=getchar();}
while(c>='0' && c<='9'){
s=s*10+c-'0';c=getchar();
}
return s*x;
}
}using namespace IO_BUFF;
/*namespace CFConTest{
const int mod=998244353;
inline int add(const int &x,const int &y){
return (x+y>=mod?x+y-mod:x+y);
}
inline int del(const int &x,const int &y){
return (x-y<0?x-y+mod:x-y);
}
int ksm(int x,int k){
int base=1;
while(k){
if(k&1)base=1ll*base*x%mod;
k>>=1;
x=1ll*x*x%mod;
}
return base;
}
};
using namespace CFConTest;*/
const int N=2e5+5;
int n,x[N],y[N];
signed main(){
#ifdef newbiewzs
freopen("data.in","r",stdin);
#else
#endif
while(cin>>n){
for(int i=1;i<=n;i++)x[i]=read(),y[i]=read();
map<int,int>mx,my;int maxx=0;
for(int i=1;i<=n;i++){
mx[x[i]]++;
my[y[i]]++;
maxx=max(maxx,mx[x[i]]);
maxx=max(maxx,my[y[i]]);
}
for(int i=1;i<=8;i++){
int u=rend(n);
map<double,int>tmp;
for(int k=1;k<=n;k++){
if(x[k]==x[u] || y[k]==y[u])continue;
double K=1.0*(x[u]-x[k])/(y[u]-y[k]);
tmp[K]++;
maxx=max(maxx,tmp[K]+1);
}
}
if(2*(n-maxx)>maxx)cout<<(n%3)<<'\n';
else {
cout<<maxx-2*(n-maxx)<<'\n';
}
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 7592kb
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: 0
Accepted
time: 4ms
memory: 5668kb
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 0 0 0 0 0 0 0 3 0 6
result:
ok 22 lines
Test #3:
score: 0
Accepted
time: 2ms
memory: 5664kb
input:
7 0 1 0 0 7 7 6 2 6 9 4 4 3 5 7 3 7 3 2 9 1 0 6 1 8 5 0 9 5 7 3 7 2 3 4 5 6 7 7 7 5 8 4 7 7 1 6 5 7 7 2 3 5 0 8 8 8 3 8 7 1 8 3 4 8 8 1 9 7 8 1 7 0 0 7 6 9 2 7 4 5 2 1 4 6 2 3 7 6 7 3 1 1 9 5 7 6 6 5 2 5 1 5 3 7 6 4 1 6 7 3 5 4 2 3 0 0 3 2 7 2 9 4 9 8 9 8 0 1 7 2 6 6 2 7 3 5 4 0 4 1 4 3 0 8 4 7 4 6 ...
output:
1 1 1 1 1 1 1 1 1 1 1 4 1 1 1 1 1 1 1 1 1
result:
ok 21 lines
Test #4:
score: 0
Accepted
time: 0ms
memory: 7600kb
input:
8 3 2 4 4 3 9 7 9 9 3 9 1 4 2 5 3 8 0 6 0 2 1 6 9 9 5 5 8 4 6 8 0 9 8 1 8 8 1 9 0 1 3 6 4 3 6 4 0 1 6 8 5 3 1 0 0 1 7 1 3 7 8 8 6 4 6 2 8 3 3 7 8 0 8 6 3 0 4 2 3 5 3 5 4 8 6 2 9 7 3 2 6 5 2 2 1 5 4 7 2 5 8 1 1 1 0 1 5 2 8 8 9 8 8 0 0 1 4 8 8 0 3 3 8 2 5 5 3 0 0 0 6 2 8 9 8 3 9 3 5 3 1 6 5 6 2 1 1 8 ...
output:
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
result:
ok 57 lines
Test #5:
score: 0
Accepted
time: 2ms
memory: 7628kb
input:
9 14 16 8 14 18 19 0 10 5 9 0 5 1 2 12 9 15 11 9 16 12 3 9 10 14 17 14 6 10 2 19 17 17 0 13 7 2 9 17 1 14 13 5 14 9 2 13 0 1 18 17 13 11 3 5 13 9 13 0 13 3 5 4 6 14 3 5 17 14 5 17 19 17 5 6 9 3 18 18 9 14 14 6 4 17 10 16 15 8 14 10 14 18 16 9 17 10 19 19 1 16 18 17 9 13 10 15 19 3 6 16 17 16 9 13 2 ...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
result:
ok 86 lines
Test #6:
score: 0
Accepted
time: 139ms
memory: 7728kb
input:
17 87310293 387438180 71556828 322852519 229718797 511837973 310313906 370688881 259858018 463145945 252802375 462493335 347775953 550587600 68053426 326582700 386313403 373022317 211296869 571386994 138237064 241008526 196230475 364801713 327348063 266915603 238976759 498766159 215667837 559919342 ...
output:
2 1 0 1 2 2 2 1 2 1 2 4 1 1 2 1 12 1 0 4 2 1 1 6 2 1 0 0 2 2 2 3 1 2 0 2 1 0 13 1 0 1 4 2 1 2 2 8 1 0 1 0 0 0 2 3 1 9 0 2 0 2 20 7 2 8 1 0 8 0 3 7 0 8 14 1 0 2 2 3 0 0 1 1 15 1 1 1 0 2 2 2 4 1 1 1 1 1 0 2 2 11 2 0 0 2 1 8 2 5 0 2 1 0 0 1 8 2 1 0 0 1 1 0 1 9 1 2 7 1 4 7 0 0 1 0 0 0 2 2 2 18 1 2 0 0 0...
result:
ok 10000 lines
Test #7:
score: 0
Accepted
time: 160ms
memory: 5712kb
input:
42 287252230 499236706 148773418 586949728 167210058 575271888 85809270 626831466 382208482 439091044 366321992 449153609 390308514 433960452 343740886 463456570 180682406 566738450 384441280 437676781 259245916 516976015 185132890 563919496 240132841 463148835 99194724 618353067 157153022 581642054...
output:
30 116 1 38 2 6 81 79 1 0 1 0 70 0 0 0 3 4 2 1 0 2 2 123 2 126 2 2 2 1 3 0 2 1 0 13 0 0 1 1 2 0 1 83 2 1 0 2 27 18 64 4 1 0 1 105 0 88 1 2 1 1 0 2 26 1 2 0 78 25 31 0 0 0 2 55 2 31 1 1 0 1 1 0 0 2 0 1 19 0 2 2 52 2 2 2 0 2 1 2 1 0 1 1 125 2 24 2 0 0 89 2 1 20 1 1 2 0 6 42 1 0 39 0 22 68 1 122 0 2 1 ...
result:
ok 1000 lines
Test #8:
score: 0
Accepted
time: 166ms
memory: 6156kb
input:
897 350467692 235711852 389244234 222063368 420837716 381703650 283369806 495010048 184447118 330280428 310297010 390950504 214233834 528051332 354440638 220358496 265847546 562724408 282462038 498518096 427605198 245483822 352161478 229166256 336628126 289194528 276162282 426888360 260597130 417944...
output:
0 2 142 1 113 1 1037 843 0 2 0 0 0 2 266 1 0 34 0 0 2 2 2 483 1 336 0 257 1 1 2 2 1 2 1469 1 2 1 199 1353 1 1 0 0 1 0 0 2 0 582 177 0 1 483 0 1 1 37 2 2 1 1 2 0 2 0 2 1 0 685 797 2 160 98 1 0 2 391 12 0 0 711 1 1 1 0 622 1 102 0 2 1 0 1 1 2 1 0 1 1
result:
ok 100 lines
Test #9:
score: 0
Accepted
time: 353ms
memory: 11508kb
input:
20000 484231306 551517006 420281290 551091920 359676382 608733140 81227614 520320566 563828247 414564665 609175198 674071338 280942605 683616695 602064645 378198095 684292446 299991380 120008991 471514239 482864858 491568800 790812451 579371035 534625299 749120999 301947770 663638720 376253692 59296...
output:
4316 17147 2351 14579 8450 19169 12743 14672 2894 2720
result:
ok 10 lines
Test #10:
score: -100
Time Limit Exceeded
input:
200000 147648030 393318930 193701587 354316868 36770429 487219496 94180290 602586130 269963274 576506160 136037810 403151450 262181052 599365328 168214029 375901896 54406410 472283850 214489917 384804834 104307628 430023262 71647492 457682638 21519941 500134904 78059629 452252296 137445999 401958876...