[bzoj 1610: [Usaco 2008 Feb] Line 연결 게임] 매 거 진

3405 단어 매 거
제목:http://www.lydsy.com/JudgeOnline/problem.php?id=1610 1610: [Usaco 2008 Feb] Line 연결 게임 시간 제한: 5 Sec Memory Limit: 64 MB 제출: 1798 해결: 808 [제출] [상태] [토론] 설명
파 머 존 은 최근 비범 하 다 고 자부 하 는 베 시 를 시험 하기 위해 게임 을 발명 했다.게임 이 시 작 될 때 FJ 는 베 시 에 게 N (2 < = N < = 200) 개의 겹 치지 않 는 점 이 그 려 진 널 빤 지 를 주 는데 그 중에서 i 번 째 점 의 가로, 세로 좌 표 는 각각 X 이다.i 와 Yi (-1,000 <= X_i <=1,000; -1,000 <= Y_i <= 1,000)。 베 시 는 두 개의 점 을 선택 하여 그들의 직선 을 통과 할 수 있 고 평면 에 만 직선 과 평행 하 는 직선 이 존재 하지 않 는 다.게임 이 끝 났 을 때 베 시의 점 수 는 바로 그녀 가 그린 직선 의 총 갯 수 였 다.베 시 는 게임 에서 이기 기 위해 당신 을 찾 았 습 니 다. 당신 이 그녀 를 도와 최대한 의 점 수 를 계산 해 주 기 를 바 랍 니 다.
Input
  • 첫 번 째 줄: 정수 1 개 입력: N
  • 2 번 째. N + 1 번 째 줄: i + 1 번 째 줄 을 빈 칸 으로 나 눈 정수 Xi、Y_i, 점 i 의 좌 표를 묘사 했다

  • Output
    첫 번 째 줄: 1 개의 정 수 를 출력 하면 베 시의 최대 점 수 를 나타 낸다. 즉, 그녀 가 그 릴 수 있 는 서로 평행 하지 않 은 직선 수 이다.
    Sample Input
    4
    -1 1
    -2 0
    0 0
    1 1
    Sample Output
  • 첫 번 째 줄: 1 개의 정 수 를 출력 하면 베 시의 최대 점 수 를 나타 낸다. 즉, 그녀 가 그 릴 수 있 는 서로 평행 하지 않 은 직선 수
  • 이다.
    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;
    }

    좋은 웹페이지 즐겨찾기