[bzoj 1610: [Usaco 2008 Feb] Line 연결 게임] 매 거 진
3405 단어 매 거
파 머 존 은 최근 비범 하 다 고 자부 하 는 베 시 를 시험 하기 위해 게임 을 발명 했다.게임 이 시 작 될 때 FJ 는 베 시 에 게 N (2 < = N < = 200) 개의 겹 치지 않 는 점 이 그 려 진 널 빤 지 를 주 는데 그 중에서 i 번 째 점 의 가로, 세로 좌 표 는 각각 X 이다.i 와 Yi (-1,000 <= X_i <=1,000； -1,000 <= Y_i <= 1,000)。 베 시 는 두 개의 점 을 선택 하여 그들의 직선 을 통과 할 수 있 고 평면 에 만 직선 과 평행 하 는 직선 이 존재 하지 않 는 다.게임 이 끝 났 을 때 베 시의 점 수 는 바로 그녀 가 그린 직선 의 총 갯 수 였 다.베 시 는 게임 에서 이기 기 위해 당신 을 찾 았 습 니 다. 당신 이 그녀 를 도와 최대한 의 점 수 를 계산 해 주 기 를 바 랍 니 다.
Input
Output
첫 번 째 줄: 1 개의 정 수 를 출력 하면 베 시의 최대 점 수 를 나타 낸다. 즉, 그녀 가 그 릴 수 있 는 서로 평행 하지 않 은 직선 수 이다.
Sample Input
4
-1 1
-2 0
0 0
1 1
Sample Output
HINT
4 출력 설명: 베 시 는 다음 과 같은 4 가지 경사 율 의 직선 을 그 릴 수 있다. - 1, 0, 1 / 3 과 1.
Source
Silver
사고방식: n ^ 2 매 거 하면 됩 니 다.
코드:
#include<iostream>
#include<stdio.h>
#include<map>
using namespace std;
struct node
{
int x,y;
}a[205];
int n;
int ans;
map<double,bool> vis;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d",&a[i].x,&a[i].y);
int flag=0;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
{
if(a[i].y-a[j].y==0)
{
if(!flag)
{
flag=1;
ans++;
}
}
else
{
double k=(double)(a[i].x-a[j].x)/(double)(a[i].y-a[j].y);
if(!vis[k])
{
vis[k]=1;
ans++;
}
}
}
cout<<ans<<endl;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
구간 중수i ~ j 블록 의 답 (복잡 도 는 n * sqrt (n) 내 에서 보장 할 수 있 습 니 다) 을 미리 처리 하 는 것 입 니 다. 만약 에 L 이 x 블록 에 속 하고 R 이 y 블록 에 속한다 고 가정 하면 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
