import java.util.ArrayList; import java.util.HashSet; import java.util.List; import java.util.Scanner; import java.util.Set; public class Main { private static final int BLOCK_SIZE = 200; private static Set[][] leftOfCoinSet = new Set[20000 / BLOCK_SIZE + 1][20000 / BLOCK_SIZE + 1]; public static void main(String[] args) { Scanner cin = new Scanner(System.in); int limit = cin.nextInt(); int leftCount = 0; for (int i = 0; i < limit; i++) { int x = cin.nextInt(); int y = cin.nextInt(); /* x,yそれぞれ1/200して、200*200の範囲内で干渉しあう円の中心情報を得る */ if (isLeft(x, y)) { leftCount++; } } System.out.println(leftCount); } private static boolean isLeft(int x, int y) { Point thisCoin = new Point(x, y); /* 落ちたコインの中心座標からブロックを求める */ int blockX = x / BLOCK_SIZE; int blockY = y / BLOCK_SIZE; /* どのブロックにまたがっているか。順に左、右、下、上、左下、右下、左上、右上で8要素配列 */ boolean[] isStradding = new boolean[4]; List> checkPointList = new ArrayList>(); if (leftOfCoinSet[blockX][blockY] == null) { leftOfCoinSet[blockX][blockY] = new HashSet(); } checkPointList.add(leftOfCoinSet[blockX][blockY]); if (blockX > 0 && x % BLOCK_SIZE < 10) { /* 左チェック。左端以外のBlockでかつ、x座標をBLOCK_SIZEで割った時の余りが半径の10に満たない場合 */ isStradding[0] = true; if (leftOfCoinSet[blockX - 1][blockY] == null) { leftOfCoinSet[blockX - 1][blockY] = new HashSet(); } checkPointList.add(leftOfCoinSet[blockX - 1][blockY]); } else if (blockX < 20000 / BLOCK_SIZE && x % BLOCK_SIZE >= BLOCK_SIZE - 10) { /* 右チェック。右端以外のBlockでかつ、x座標をBLOCK_SIZEで割った時の余りがBLOCK_SIZEから半径の10を引いた値以上になる場合 */ isStradding[1] = true; if (leftOfCoinSet[blockX + 1][blockY] == null) { leftOfCoinSet[blockX + 1][blockY] = new HashSet(); } checkPointList.add(leftOfCoinSet[blockX + 1][blockY]); } if (blockY > 0 && y % BLOCK_SIZE < 10) { /* 下チェック。下端以外のBlockでかつ、y座標をBLOCK_SIZEで割った時の余りが半径の10に満たない場合 */ isStradding[2] = true; if (leftOfCoinSet[blockX][blockY - 1] == null) { leftOfCoinSet[blockX][blockY - 1] = new HashSet(); } checkPointList.add(leftOfCoinSet[blockX][blockY - 1]); } else if (blockY < 20000 / BLOCK_SIZE && y % BLOCK_SIZE >= BLOCK_SIZE - 10) { /* 右チェック。右端以外のBlockでかつ、x座標をBLOCK_SIZEで割った時の余りがBLOCK_SIZEから半径の10を引いた値以上になる場合 */ isStradding[3] = true; if (leftOfCoinSet[blockX][blockY + 1] == null) { leftOfCoinSet[blockX][blockY + 1] = new HashSet(); } checkPointList.add(leftOfCoinSet[blockX][blockY + 1]); } if (isStradding[0] && isStradding[2]) { /* 左と下両方にはみ出ている場合のみ、追加で左下ブロックを判定 */ if (thisCoin.getDistance(blockX * BLOCK_SIZE - 1, blockY * BLOCK_SIZE - 1) < 100) { if (leftOfCoinSet[blockX - 1][blockY - 1] == null) { leftOfCoinSet[blockX - 1][blockY - 1] = new HashSet(); } checkPointList.add(leftOfCoinSet[blockX - 1][blockY - 1]); } } else if (isStradding[0] && isStradding[3]) { /* 左と上両方にはみ出ている場合のみ、追加で左上ブロックを判定 */ if (thisCoin.getDistance(blockX * BLOCK_SIZE - 1, (blockY + 1) * BLOCK_SIZE) < 100) { if (leftOfCoinSet[blockX - 1][blockY + 1] == null) { leftOfCoinSet[blockX - 1][blockY + 1] = new HashSet(); } checkPointList.add(leftOfCoinSet[blockX - 1][blockY + 1]); } } else if (isStradding[1] && isStradding[2]) { /* 右と下両方にはみ出ている場合のみ、追加で右下ブロックを判定 */ if (thisCoin.getDistance((blockX + 1) * BLOCK_SIZE, blockY * BLOCK_SIZE - 1) < 100) { if (leftOfCoinSet[blockX + 1][blockY - 1] == null) { leftOfCoinSet[blockX + 1][blockY - 1] = new HashSet(); } checkPointList.add(leftOfCoinSet[blockX + 1][blockY - 1]); } } else if (isStradding[1] && isStradding[3]) { /* 右と上両方にはみ出ている場合のみ、追加で右上ブロックを判定 */ if (thisCoin.getDistance((blockX + 1) * BLOCK_SIZE, (blockY + 1) * BLOCK_SIZE) < 100) { if (leftOfCoinSet[blockX + 1][blockY + 1] == null) { leftOfCoinSet[blockX + 1][blockY + 1] = new HashSet(); } checkPointList.add(leftOfCoinSet[blockX + 1][blockY + 1]); } } return checkDistance(thisCoin, checkPointList); } private static boolean checkDistance(Point point, List> leftCoinSetList) { for (Set leftCoinSet : leftCoinSetList) { for (Point leftPoint : leftCoinSet) { if (leftPoint.getDistance(point) < 400) { return false; } } } for (Set leftCoinSet : leftCoinSetList) { leftCoinSet.add(point); } /* 全てチェックOKならば、チェックした対象のSetに対して自分自身を追加する */ return true; } static class Point { int x; int y; Point(int x, int y) { this.x = x; this.y = y; } public boolean equals(Point other) { return x == other.x && y == other.y; } public int getDistance(int otherX, int otherY) { return (x - otherX) * (x - otherX) + (y - otherY) * (y - otherY); } public int getDistance(Point other) { return (x - other.x) * (x - other.x) + (y - other.y) * (y - other.y); } } }