Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.
Нена је синоћ сањала да гледа у звездано небо, које се може замислити као дводимензиона раван, у којој се налазе звезде, које су представљене као тачке. Када се пробудила, поред тога што је схватила да касни, заборавила је скоро све детаље свог сна. Једино што је запамтила је \(K\), број колинеарних тројки тачака. Формално, ако су звезде биле различите тачке \(A_1, A_2, \ldots, A_N\), број колинеарних тројки је број уређених тројки \((i,j,k)\) таквих да је \(1 \leq i < j < k \leq N\) и тачке \(A_i, A_j, A_k\) су колинеарне.
Помозите Нени тако што ћете јој рећи један скуп са највише \(2000\) различитих тачака за који важи да је број колинеарних тројки тачно \(K\). Нена воли целе бројеве, а не воли бројеве којима је апсолутна вредност већа од \(10^9\), па координате вашег скупа тачака такође морају задовољавати ове особине. Није потребно минимизовати број тачака. Гарантује се да под датим ограничењима увек постоји бар једно решење.
У првом и једином реду стандардног улаза налази се један цео број \(K\), тражени број колинеарних тројки.
У први ред стандардног излаза исписати природан број \(N\), број тачака. У наредних \(N\) редова исписати целе бројеве \(x_i, y_i\), координате тачке \(A_i\). За ове бројеве мора да важи \(-10^9 \leq x_i, y_i \leq 10^9\). Све одштампане тачке морају бити различите.
89
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 225
0 2
0 1
0 0
1 0
2 044
0 0
1 1
2 2
3 3У првом примеру тачке формирају квадратну мрежу формата \(3 \times 3\). Постоје \(3\) колинеарне тројке по врстама, \(3\) колинеарне тројке по колонама и \(2\) колинеарне тројке по дијагоналама, што је укупно \(8\) колинеарних тројки.
У другом примеру, прве три тачке чине једну колинеарну тројку, а последње три тачке другу колинеарну тројку.
У трећем примеру, свака тројка је колинеарна, таквих тројки има \(4\).
Тест примери су подељени у 4 дисјунктне групе: - У тест примерима вредним 20 поена: \(K \le 10\). - У тест примерима вредним 20 поена: \(K \leq 2000\). - У тест примерима вредним 20 поена: \(K \leq 10^6\). - У тест примерима вредним 40 поена: нема додатних ограничења.