POJ 2606 Rabbit hunt(내 수제의 길--사율이 가장 많다)
Time Limit: 1000MS
Memory Limit: 65536K
Total Submissions: 6159
Accepted: 3008
Description
A good hunter kills two rabbits with one shot. Of course, it can be easily done since for any two points we can always draw a line containing the both. But killing three or more rabbits in one shot is much more difficult task. To be the best hunter in the world one should be able to kill the maximal possible number of rabbits. Assume that rabbit is a point on the plane with integer x and y coordinates. Having a set of rabbits you are to find the largest number K of rabbits that can be killed with single shot, i.e. maximum number of points lying exactly on the same line. No two rabbits sit at one point.
Input
An input contains an integer N (2<=N<=200) specifying the number of rabbits. Each of the next N lines in the input contains the x coordinate and the y coordinate (in this order) separated by a space (-1000<=x,y<=1000).
Output
The output contains the maximal number K of rabbits situated in one line.
Sample Input
6
7 122
8 139
9 156
10 173
11 190
-100 1
Sample Output
5
Source
Ural State University collegiate programming contest 2000
n개의 점이 있는데, 최대 몇 개의 점이 공통되어 있는지 물어본다.
직접copy의 1118 코드.해법 상세: POJ 1118의 문제 풀이 보고서
참고 사항:
1) 두 문제의 종료 조건이 다르다.(1OLE)
코드(1AC 1OLE):
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int aid[1000][2];
float xielv[1000];
int main(void){
int i, j, k;
int max, tmp;
int n;
while (scanf("%d", &n) != EOF){
memset(aid, 0, sizeof(aid));
for (i = 0; i < n; i++){
scanf("%d%d", &aid[i][0], &aid[i][1]);
}
max = 2;
for (i = 0; i < n - 1; i++){
for (j = i + 1, k = 0; j < n; j++){
if (aid[j][0] == aid[i][0]){
xielv[k++] = 32767;
}
else{
xielv[k++] = (float)(aid[j][1] - aid[i][1]) / (float)(aid[j][0] - aid[i][0]);
}
}
sort(xielv, xielv + k);
for (j = 1, tmp = 2; j <= k; j++){
if (xielv[j] == xielv[j - 1]){
tmp ++;
if (tmp > max){
max = tmp;
}
}
else{
tmp = 2;
}
}
}
printf("%d
", max);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
POJ 2606 Rabbit hunt(내 수제의 길--사율이 가장 많다)Rabbit hunt Time Limit: 1000MS Memory Limit: 65536K A good hunter kills two rabbits with one shot. Of course, it can be ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.