[SOLUTION] Off by One solution codeforces – There are nn points on an infinite plane, 2021

Off by One solution codeforces

Off by One solution codeforces

There are nn points on an infinite plane. The ii-th point has coordinates (xi,yi)(xi,yi) such that xi>0xi>0 and yi>0yi>0. The coordinates are not necessarily integer.

In one move you perform the following operations:

  • choose two points aa and bb (aba≠b);
  • move point aa from (xa,ya)(xa,ya) to either (xa+1,ya)(xa+1,ya) or (xa,ya+1)(xa,ya+1);
  • move point bb from (xb,yb)(xb,yb) to either (xb+1,yb)(xb+1,yb) or (xb,yb+1)(xb,yb+1);
  • remove points aa and bb.

However, the move can only be performed if there exists a line that passes through the new coordinates of aa, new coordinates of bb and (0,0)(0,0).

Otherwise, the move can’t be performed and the points stay at their original coordinates (xa,ya)(xa,ya) and (xb,yb)(xb,yb), respectively.

The numeration of points does not change after some points are removed. Once the points are removed, they can’t be chosen in any later moves. Note that you have to move both points during the move, you can’t leave them at their original coordinates.

What is the maximum number of moves you can perform? What are these moves?

If there are multiple answers, you can print any of them.

Off by One solution codeforces

Input : Off by One solution codeforces

The first line contains a single integer nn (1n21051≤n≤2⋅105) — the number of points.

The ii-th of the next nn lines contains four integers ai,bi,ci,diai,bi,ci,di (1ai,bi,ci,di1091≤ai,bi,ci,di≤109). The coordinates of the ii-th point are xi=aibixi=aibi and yi=cidiyi=cidi.

Output: Off by One solution codeforces

In the first line print a single integer cc — the maximum number of moves you can perform.

Each of the next cc lines should contain a description of a move: two integers aa and bb (1a,bn1≤a,b≤naba≠b) — the points that are removed during the current move. There should be a way to move points aa and bb according to the statement so that there’s a line that passes through the new coordinates of aa, the new coordinates of bb and (0,0)(0,0). No removed point can be chosen in a later move.

If there are multiple answers, you can print any of them. You can print the moves and the points in the move in the arbitrary order.

Examples Off by One solution codeforces

input Off by One solution codeforces

Copy Off by One solution codeforces
7 
4 1 5 1
1 1 1 1
3 3 3 3
1 1 4 1
6 1 1 1
5 1 4 1
6 1 1 1

output

Copy
3
1 6
2 4
5 7

input

Copy
4
2 1 1 1
1 1 2 1
2 1 1 2
1 2 1 2

output

Copy
1
1 2

input

Copy
4
182 168 60 96
78 72 45 72
69 21 144 63
148 12 105 6

output

Copy
1
2 4
Note

Here are the points and the moves for the ones that get chosen for the moves from the first example:

Off by One solution codeforces

PROGRAM CODE:

JAVA

import java.io.*;
import java.util.*;

public class CF1519E extends PrintWriter {
CF1519E() { super(System.out); }
Scanner sc = new Scanner(System.in);
public static void main(String[] $) {
CF1519E o = new CF1519E(); o.main(); o.flush();
}

long gcd(long a, long b) {
return b == 0 ? a : gcd(b, a % b);
}
int[] dd, eo; int[][] eh;
int[] ij, ans; int cnt;
void init(int n, int m) {
dd = new int[n]; Arrays.fill(dd, -1);
eo = new int[n]; eh = new int[n][2];
ij = new int[m]; ans = new int[m];
}
void append(int i, int h) {
int o = eo[i]++;
if (o >= 2 && (o & o - 1) == 0)
eh[i] = Arrays.copyOf(eh[i], o << 1);
eh[i][o] = h;
}
boolean dfs(int hp, int i, int d) {
dd[i] = d;
int h_ = -1;
for (int o = eo[i]; o-- > 0; ) {
int h = eh[i][o];
if (h == hp)
continue;
int j = i ^ ij[h];
if (dd[j] != -1 && dd[j] < d || dd[j] == -1 && dfs(h, j, d + 1)) {
if (h_ == -1)
h_ = h;
else {
ans[cnt++] = h_;
ans[cnt++] = h;
h_ = -1;
}
}
}
if (h_ != -1 && hp != -1) {
ans[cnt++] = h_;
ans[cnt++] = hp;
return false;
}
return true;
}
void main() {
int n = sc.nextInt();
long[] aa = new long[n * 4];
for (int i = 0; i < n; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
int d = sc.nextInt();
long p, q, z;
// (c / d) / ((a + b) / b)
p = (long) c * b;
q = (long) d * (a + b);
z = gcd(p, q); p /= z; q /= z;
aa[i << 2 | 0] = p;
aa[i << 2 | 1] = q;
// ((c + d) / d) / (a / b)
p = (long) (c + d) * b;
q = (long) d * a;
z = gcd(p, q); p /= z; q /= z;
aa[i << 2 | 2] = p;
aa[i << 2 | 3] = q;
}
Integer[] hh = new Integer[n * 2];
for (int h = 0; h < n * 2; h++)
hh[h] = h;
Arrays.sort(hh, (i, j) -> Long.signum(
aa[i << 1] != aa[j << 1] ? aa[i << 1] - aa[j << 1] : aa[i << 1 | 1] - aa[j << 1 | 1]));
int[] cc = new int[n * 2];
int k = 0;
for (int h = 0; h < n * 2; h++)
cc[hh[h]] = h + 1 == n * 2 || aa[hh[h] << 1] != aa[hh[h + 1] << 1] || aa[hh[h] << 1 | 1] != aa[hh[h + 1] << 1 | 1] ? k++ : k;
init(k, n);
for (int h = 0; h < n; h++) {
int i = cc[h << 1];
int j = cc[h << 1 | 1];
ij[h] = i ^ j;
append(i, h);
append(j, h);
}
for (int h = 0; h < k; h++)
if (dd[h] == -1)
dfs(-1, h, 0);
println(cnt / 2);
for (int h = 0; h < cnt; h += 2)
println((ans[h] + 1) + " " + (ans[h + 1] + 1));
}
}

PYTHON

import sys
from sys import stdin
import math
from collections import deque
n = int(stdin.readline())
dic = {}
lis = []
for i in range(n):
a,b,c,d = map(int,stdin.readline().split())
A,B,C,D = a+b,b,c,d
siA = C * B
boA = D * A

g = math.gcd(siA,boA)
siA //= g
boA //= g

if (siA,boA) not in dic:
dic[(siA,boA)] = len(dic)
lis.append([])

A,B,C,D = a,b,c+d,d

siB = C * B
boB = D * A

g = math.gcd(siB,boB)
siB //= g
boB //= g

if (siB,boB) not in dic:
dic[(siB,boB)] = len(dic)
lis.append([])

va = dic[(siA,boA)]
vb = dic[(siB,boB)]

lis[va].append( (vb,i) )
lis[vb].append( (va,i) )

ans = []
used = [False] * (3*n)
nexedge = [0] * (3*n)
able = [True] * (3*n)
pedge = [None] * (3*n)
for v in range(len(lis)):

if not able[v]:
continue

stk = [v]
able[v] = False


while stk:

v = stk[-1]

if len(lis[v]) <= nexedge[v]:

elis = []
for nex,ind in lis[v]:
if ind != pedge[v] and not used[ind]:
elis.append(ind)

if pedge[v] != None and not used[pedge[v]]:
elis.append(pedge[v])

for i in range(1,len(elis),2):
ans.append( (elis[i-1]+1,elis[i]+1) )
used[elis[i-1]] = True
used[elis[i]] = True

del stk[-1]
continue

nex,ind = lis[v][nexedge[v]]
nexedge[v] += 1

if able[nex]:
pedge[nex] = ind
able[nex] = False
stk.append(nex)

print (len(ans))
for i in ans:
print (*i)

Go

package main
import("bufio";."fmt";"os")

// github.com/EndlessCheng/codeforces-go
func main() {
in := bufio.NewReader(os.Stdin)
out := bufio.NewWriter(os.Stdout)
defer out.Flush()

id := map[[2]int64]int{}
e := func(x, y int64) int {
a, b := x, y
for a > 0 {
a, b = b%a, a
}
p := [2]int64{x/b, y/b}
if _, ok := id[p]; !ok {
id[p] = len(id)
}
return id[p]
}
var n, s int
var a, b, c, d int64
Fscan(in, &n)
type nb struct{ w, i int }
g := make([][]nb, 2*n)
for i := 1; i <= n; i++ {
Fscan(in, &a, &b, &c, &d)
v, w := e(b*c, (a+b)*d), e(b*(c+d), a*d)
g[v] = append(g[v], nb{w, i})
g[w] = append(g[w], nb{v, i})
}

ds := make([][]int, len(id))
vis := make([]int, len(id))
var f func(int, int)
f = func(v, p int) {
vis[v] = 1
for _, e := range g[v] {
w,i:= e.w,e.i
if i == p || vis[w] == 2 {
continue
}
if vis[w] > 0 {
ds[v] = append(ds[v], i)
} else {
f(w, i)
if len(ds[w])&1 > 0 {
ds[w] = append(ds[w], i)
} else {
ds[v] = append(ds[v], i)
}
}
}
vis[v] = 2
}
for i, b := range vis {
if b == 0 {
f(i, 0)
}
}

for _, d := range ds {
s += len(d) / 2
}
Fprintln(out, s)
for _, d := range ds {
for i := 0; i+1 < len(d); i += 2 {
Fprintln(out, d[i], d[i+1])
}
}
}

C++

#include<bits/stdc++.h>
#define int long long
using namespace std;
map<pair<int,int>,int>tong;
vector<pair<int,int> >ans,e[400010];
int vis[400010],fi[400010];
int n,tot;
int dfs(int u){
vis[u]=1;
int cur=-1;
for(auto i:e[u]){
if(vis[i.first]){
if(fi[i.first]){
if(cur==-1) cur=i.second;
else{
ans.push_back({cur,i.second});
cur=-1;
}
}
continue;
}
int lst=dfs(i.first);
if(lst!=-1) ans.push_back({i.second,lst});
else{
if(cur==-1) cur=i.second;
else{
ans.push_back({cur,i.second});
cur=-1;
}
}
}
fi[u]=1;
return cur;
}
signed main(){
scanf("%lld",&n);
tot=0;
for(int i=1;i<=n;i++){
int a,b,c,d;
scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
int x,y;
x=(a+b)*d,y=b*c;
int gcd=__gcd(x,y);
x/=gcd,y/=gcd;
int u,v;
u=tong[{x,y}];
if(u==0){
tong[{x,y}]=++tot;
u=tot;
}
x=a*d,y=b*(c+d);
gcd=__gcd(x,y);
x/=gcd,y/=gcd;
v=tong[{x,y}];
if(v==0){
tong[{x,y}]=++tot;
v=tot;
}
e[u].push_back({v,i});
e[v].push_back({u,i});
} 
memset(vis,0,sizeof(vis));
for(int i=1;i<=tot;i++){
if(!vis[i]) dfs(i);
}
printf("%lld\n",(int)ans.size());
for(auto i:ans) printf("%lld %lld\n",i.first,i.second);
return 0;
}
Off by One solution codeforces
Off by One solution codeforces, Off by One solution codeforces, Off by One solution codeforces, Off by One solution codeforces, Off by One solution codeforces, Off by One solution codeforces, Off by One solution codeforces, Off by One solution codeforces

Also read : Flower Sequence solution codechef 2021 

 

Leave a Comment