10523번 - 직선 찾기 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4 초 | 256 MB | 2027 | 374 | 221 | 15.911% |
문제
N개의 점이 좌표 평면 상에 있을 때, 이 중 p 퍼센트 이상의 점들을 지나는 직선이 존재하는지 판별하시오. 즉, 0.01Np개 이상의 점을 지나는 직선이 존재하는지를 판별하시오.
입력
입력은
- 첫 번째 줄에 점의 수 n (1 ≤ n ≤ 105)
- 두 번째 줄에 직선이 지나야 하는 점의 퍼센티지 p (20 ≤ p ≤ 100)
- 이후 n개의 줄에 점의 좌표 x, y (0 ≤ x, y ≤ 109)
의 형태로 주어진다.
주어지는 모든 점들은 서로 다르다.
출력
그러한 직선이 존재하면 possible, 존재하지 않는다면 impossible을 출력한다.
예제 입력 1
5 55 0 0 10 10 10 0 0 10 3 3
예제 출력 1
possible
예제 입력 2
5 45 0 0 10 10 10 0 0 10 3 4
예제 출력 2
impossible
힌트
입력 예제 1에서 (0, 0) / (3, 3) / (10, 10)을 지나는 직선을 찾을 수 있다. 2.75개 이상의 점을 지났으니 그러한 직선이 있다고 볼 수 있다.
출처
ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2014 F번
- 문제를 번역한 사람: koosaga
- 문제를 만든 사람: Alexander Rass
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호