문제
KSA의 1학년 학생들은 매일 아침 졸업을 하기 위해 아침 태권도를 해야 한다.
태권도장은 2차원 좌표평면으로 표현할 수 있고, 이때 사범님은 원점에 앉아있다. $N$명의 1학년 학생들은 1ドル$번부터 $N$번까지의 번호로 구분되며, $i$번 학생의 위치는 $(X_i, Y_i)$이다. 태권도 사범님은 $i$번 학생이 다른 학생에게 가려지지 않는 경우에만 볼 수 있다. 즉, 원점과 $(X_i, Y_i)$를 이어 선분을 만들었을 때, 선분 위에 위치한 다른 학생이 아무도 없을 때 사범님은 $i$번 학생을 볼 수 있다.
1학년 학생들은 너무 공부를 많이 하여 매우 졸리기 때문에, 사범님에게 보이는 학생들만 태권도를 열심히 한다. 학생들의 위치 정보가 주어졌을 때, 태권도를 열심히 하는 학생들은 몇 명인지 구하시오.
출력
태권도를 열심히 하는 학생들은 몇 명인지 출력한다.
제한
- 1ドル \leq N \leq 2 \times 10^5$
- $-10^4 \leq X_i, Y_i \leq 10^4$
- 모든 $i$에 대해 $(X_i, Y_i) \neq (0, 0)$
- $(X_i, Y_i) = (X_j, Y_j)$인 서로 다른 $i,ドル $j$가 존재하지 않음
서브태스크
| 번호 | 배점 | 제한 | | 1 | 10 | 0ドル < X_i, Y_i \leq 50$ $(1 \le i \le N)$
|
| 2 | 30 | $N \le 3000$
|
| 3 | 60 | 추가 제약 조건 없음
|
빨간색 정사각형으로 표시된 4ドル$명의 학생들만 태권도를 열심히 한다.
W3sicHJvYmxlbV9pZCI6IjI5MTk3IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjNTQ0XHVjZTY4IFx1ZDBkY1x1YWQ4Y1x1YjNjNCIsImRlc2NyaXB0aW9uIjoiPHA+S1NBXHVjNzU4IDFcdWQ1NTlcdWIxNDQgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzQwIFx1YjllNFx1Yzc3YyBcdWM1NDRcdWNlNjggXHVjODc4XHVjNWM1XHVjNzQ0IFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjNTQ0XHVjZTY4IFx1ZDBkY1x1YWQ4Y1x1YjNjNFx1Yjk3YyBcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQwZGNcdWFkOGNcdWIzYzRcdWM3YTVcdWM3NDAgMlx1Y2MyOFx1YzZkMCBcdWM4OGNcdWQ0NWNcdWQzYzlcdWJhNzRcdWM3M2NcdWI4NWMgXHVkNDVjXHVkNjA0XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWFjZTAsIFx1Yzc3NFx1YjU0YyBcdWMwYWNcdWJjOTRcdWIyZDhcdWM3NDAgXHVjNmQwXHVjODEwXHVjNWQwIFx1YzU0OVx1YzU0NFx1Yzc4OFx1YjJlNC4gJE4kXHViYTg1XHVjNzU4IDFcdWQ1NTlcdWIxNDQgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzQwICQxJFx1YmM4OFx1YmQ4MFx1ZDEzMCAkTiRcdWJjODhcdWFlNGNcdWM5YzBcdWM3NTggXHViYzg4XHVkNjM4XHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YmE3MCwgJGkkXHViYzg4IFx1ZDU1OVx1YzBkZFx1Yzc1OCBcdWM3MDRcdWNlNThcdWIyOTQgJChYX2ksIFlfaSkkXHVjNzc0XHViMmU0LiBcdWQwZGNcdWFkOGNcdWIzYzQgXHVjMGFjXHViYzk0XHViMmQ4XHVjNzQwICRpJFx1YmM4OCBcdWQ1NTlcdWMwZGRcdWM3NzQgXHViMmU0XHViOTc4IFx1ZDU1OVx1YzBkZFx1YzVkMFx1YWM4YyBcdWFjMDBcdWI4MjRcdWM5YzBcdWM5YzAgXHVjNTRhXHViMjk0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjljYyBcdWJjZmMgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjOTg5LCBcdWM2ZDBcdWM4MTBcdWFjZmMgJChYX2ksIFlfaSkkXHViOTdjIFx1Yzc3NFx1YzViNCBcdWMxMjBcdWJkODRcdWM3NDQgXHViOWNjXHViNGU0XHVjNWM4XHVjNzQ0IFx1YjU0YywgXHVjMTIwXHViZDg0IFx1YzcwNFx1YzVkMCBcdWM3MDRcdWNlNThcdWQ1NWMgXHViMmU0XHViOTc4IFx1ZDU1OVx1YzBkZFx1Yzc3NCBcdWM1NDRcdWJiMzRcdWIzYzQgXHVjNWM2XHVjNzQ0IFx1YjU0YyBcdWMwYWNcdWJjOTRcdWIyZDhcdWM3NDAgJGkkXHViYzg4IFx1ZDU1OVx1YzBkZFx1Yzc0NCBcdWJjZmMgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+MVx1ZDU1OVx1YjE0NCBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NDAgXHViMTA4XHViYjM0IFx1YWNmNVx1YmQ4MFx1Yjk3YyBcdWI5Y2VcdWM3NzQgXHVkNTU4XHVjNWVjIFx1YjllNFx1YzZiMCBcdWM4NzhcdWI5YWNcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWMwYWNcdWJjOTRcdWIyZDhcdWM1ZDBcdWFjOGMgXHViY2Y0XHVjNzc0XHViMjk0IFx1ZDU1OVx1YzBkZFx1YjRlNFx1YjljYyBcdWQwZGNcdWFkOGNcdWIzYzRcdWI5N2MgXHVjNWY0XHVjMmVjXHVkNzg4IFx1ZDU1Y1x1YjJlNC4gXHVkNTU5XHVjMGRkXHViNGU0XHVjNzU4IFx1YzcwNFx1Y2U1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVkMGRjXHVhZDhjXHViM2M0XHViOTdjIFx1YzVmNFx1YzJlY1x1ZDc4OCBcdWQ1NThcdWIyOTQgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzQwIFx1YmE4NyBcdWJhODVcdWM3NzhcdWM5YzAgXHVhZDZjXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjODE1XHVjMjE4ICROJFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPiRpICsgMSRcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjQ1MCBcdWM4MTVcdWMyMTggJFhfaSwgWV9pJFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gJCgxIFxcbGVxIGkgXFxsZXEgTikkPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVkMGRjXHVhZDhjXHViM2M0XHViOTdjIFx1YzVmNFx1YzJlY1x1ZDc4OCBcdWQ1NThcdWIyOTQgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzQwIFx1YmE4NyBcdWJhODVcdWM3NzhcdWM5YzAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4kMSBcXGxlcSBOIFxcbGVxIDIgXFx0aW1lcyAxMF41JDxcL2xpPlxyXG5cdDxsaT4kLTEwXjQgXFxsZXEgWF9pLCBZX2kgXFxsZXEgMTBeNCQ8XC9saT5cclxuXHQ8bGk+XHViYWE4XHViNGUwICRpJFx1YzVkMCBcdWIzMDBcdWQ1NzQgJChYX2ksIFlfaSkgXFxuZXEgKDAsIDApJDxcL2xpPlxyXG5cdDxsaT4kKFhfaSwgWV9pKSA9IChYX2osIFlfaikkXHVjNzc4IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggJGkkLCAkaiRcdWFjMDAgXHVjODc0XHVjN2FjXHVkNTU4XHVjOWMwIFx1YzU0YVx1Yzc0YzxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazEiOiI8cD4kMCAmbHQ7IFhfaSwgWV9pIFxcbGVxIDUwJCAkKDEgXFxsZSBpIFxcbGUgTikkPFwvcD5cclxuIiwic3VidGFzazIiOiI8cD4kTiBcXGxlIDMwMDAkPFwvcD5cclxuIiwic3VidGFzazMiOiI8cD5cdWNkOTRcdWFjMDAgXHVjODFjXHVjNTdkIFx1Yzg3MFx1YWM3NCBcdWM1YzZcdWM3NGM8XC9wPlxyXG4iLCJzYW1wbGVfZXhwbGFpbl8xIjoiPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC9iY2RlZWFlZi0yOWRjLTQxMWYtYWU1Ni0zNGZmZTg1NjQ1ZWNcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwiaGVpZ2h0OiA0MzhweDsgd2lkdGg6IDQ1MHB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5cdWJlNjhcdWFjMDRcdWMwYzkgXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1XHVjNzNjXHViODVjIFx1ZDQ1Y1x1YzJkY1x1YjQxYyAkNCRcdWJhODVcdWM3NTggXHVkNTU5XHVjMGRkXHViNGU0XHViOWNjIFx1ZDBkY1x1YWQ4Y1x1YjNjNFx1Yjk3YyBcdWM1ZjRcdWMyZWNcdWQ3ODggXHVkNTVjXHViMmU0LjxcL3A+XHJcbiJ9LHsicHJvYmxlbV9pZCI6IjI5MTk3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVGFla3dvbmRvIiwiZGVzY3JpcHRpb24iOiI8cD5JbiBLU0EsIGZpcnN0LXllYXIgc3R1ZGVudHMgbXVzdCBhdHRlbmQgVGFla3dvbmRvIGNsYXNzZXMgZXZlcnkgbW9ybmluZyBhcyBhIHBhcnQgb2YgZ3JhZHVhdGlvbiByZXF1aXJlbWVudHMuPFwvcD5cclxuXHJcbjxwPlRoZSBUYWVrd29uZG8gZ3ltbmFzaXVtIGNhbiBiZSBleHByZXNzZWQgYXMgYSB0d28tZGltZW5zaW9uYWwgY29vcmRpbmF0ZSBwbGFuZSwgYW5kIHRoZSBpbnN0cnVjdG9yIGlzIHNpdHRpbmcgYXQgdGhlIG9yaWdpbi4gJE4kIGZpcnN0LXllYXIgc3R1ZGVudHMgb2YgS1NBIGFyZSBudW1iZXJlZCAkMSQgdGhyb3VnaCAkTiQuIFRoZSAkaSQtdGggc3R1ZGVudCBpcyBsb2NhdGVkIGF0ICQoWF9pLCBZX2kpJC4gVGhlIGluc3RydWN0b3IgY2FuIHNlZSB0aGUgJGkkLXRoIHN0dWRlbnQgb25seSBpZiBhbnkgb3RoZXIgc3R1ZGVudCBkb2VzIG5vdCBibG9jayB0aGUgJGkkLXRoIHN0dWRlbnQuIEluIG90aGVyIHdvcmRzLCBmb3IgdGhlIGluc3RydWN0b3IgdG8gc2VlIHRoZSAkaSQtdGggc3R1ZGVudCwgdGhlcmUgbXVzdCBiZSBubyBzdHVkZW50IG9uIHRoZSBsaW5lIHNlZ21lbnQgY29ubmVjdGluZyB0aGUgb3JpZ2luIGFuZCAkKFhfaSwgWV9pKSQuPFwvcD5cclxuXHJcbjxwPlNpbmNlIGZpcnN0LXllYXIgc3R1ZGVudHMgc3R1ZHkgdG9vIG11Y2ggYW5kIGFyZSB2ZXJ5IHNsZWVweSwgb25seSB0aGUgc3R1ZGVudHMgd2hvIHRoZSBpbnN0cnVjdG9yIGNhbiBzZWUgcHJhY3RpY2UgVGFla3dvbmRvIGhhcmQuIFdoZW4gdGhlIHN0dWRlbnRzJiMzOTsgbG9jYXRpb25zIGFyZSBnaXZlbiwgY291bnQgaG93IG1hbnkgc3R1ZGVudHMgcHJhY3RpY2UgVGFla3dvbmRvIGhhcmQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyBhbiBpbnRlZ2VyICROJC48XC9wPlxyXG5cclxuPHA+VGhlICRpICsgMSQtdGggbGluZSBjb250YWlucyB0d28gaW50ZWdlcnMgJFhfaSQgYW5kICRZX2kkLCBzZXBhcmF0ZWQgYnkgYSBzcGFjZS4gJCgxIFxcbGVxIGkgXFxsZXEgTikkPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UHJpbnQgdGhlIG51bWJlciBvZiBzdHVkZW50cyB3aG8gcHJhY3RpY2UgVGFla3dvbmRvIGhhcmQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCIsImxpbWl0IjoiPHVsPlxyXG5cdDxsaT4kMSBcXGxlcSBOIFxcbGVxIDIgXFx0aW1lcyAxMF41JDxcL2xpPlxyXG5cdDxsaT4kLTEwXjQgXFxsZXEgWF9pLCBZX2kgXFxsZXEgMTBeNCQ8XC9saT5cclxuXHQ8bGk+Rm9yIGFsbCAkaSQsICQoWF9pLCBZX2kpIFxcbmVxICgwLCAwKSQ8XC9saT5cclxuXHQ8bGk+VGhlcmUgYXJlIG5vIHR3byBkaXN0aW5jdCBpbnRlZ2VycyAkaSwgaiQgc3VjaCB0aGF0ICQoWF9pLCBZX2kpID0gKFhfaiwgWV9qKSQ8XC9saT5cclxuPFwvdWw+XHJcbiIsInN1YnRhc2sxIjoiPHA+JDAgJmx0OyBYX2ksIFlfaSBcXGxlcSA1MCQgJCgxIFxcbGUgaSBcXGxlIE4pJDxcL3A+XHJcbiIsInN1YnRhc2syIjoiPHA+JE4gXFxsZSAzMDAwJDxcL3A+XHJcbiIsInN1YnRhc2szIjoiPHA+Tm8gYWRkaXRpb25hbCBjb25zdHJhaW50czxcL3A+XHJcbiIsInNhbXBsZV9leHBsYWluXzEiOiI8cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcLzVmZDQwNTE4LTZmMjctNGRmMy05YjdhLTM1ODA1NGU4YTVjMFwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJoZWlnaHQ6IDQzOHB4OyB3aWR0aDogNDUwcHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPk9ubHkgJDQkIHN0dWRlbnRzLCBtYXJrZWQgYnkgcmVkIHNxdWFyZXMgcHJhY3RpY2UgVGFla3dvbmRvIGhhcmQuPFwvcD5cclxuIn1d