SGU120 Archipelago

3937 단어 계산 기하학sgu
SGU Archipelago
제목 의 대의
정 N 변형 의 두 정점 의 번호 와 좌 표를 제시 하고 모든 정점 의 좌 표를 순서대로 출력 합 니 다.
알고리즘 사고
기 하 를 계산 하고 주어진 두 점 과 다각형 중심 은 이등변 삼각형 을 형성 하 며, 꼭대기 의 크기 와 밑변 의 길 이 는 이미 알 고 있 으 며, 밑각 의 크기 와 경사 변 의 길 이 를 계산 할 수 있 으 며, 회전 밑변 에 대응 하 는 벡터 를 통 해 중심 좌 표를 얻 은 다음 에 중심 과 반지름 벡터 에 따라 순서대로 회전 하여 모든 좌 표를 얻 을 수 있다.
시간 복잡 도: O (N)
코드
/** * Copyright © 2015 Authors. All rights reserved. * * FileName: 120.cpp * Author: Beiyu Li <[email protected]> * Date: 2015-05-31 */
#include <bits/stdc++.h>

using namespace std;

#define rep(i,n) for (int i = 0; i < (n); ++i)
#define For(i,s,t) for (int i = (s); i <= (t); ++i)
#define foreach(i,c) for (__typeof(c.begin()) i = c.begin(); i != c.end(); ++i)

typedef long long LL;
typedef pair<int, int> Pii;

const int inf = 0x3f3f3f3f;
const LL infLL = 0x3f3f3f3f3f3f3f3fLL;

const double pi = acos(-1);

typedef complex<double> Point;
typedef complex<double> Vector;
#define X real()
#define Y imag()

Vector unit(Vector v) { return v / abs(v); }
Vector rotate(Vector v, double a) { return v * polar(1.0, a); }

const int maxn = 150 + 5;

int n, n1, n2;
Point p[maxn];

int main()
{
        scanf("%d%d%d", &n, &n1, &n2);
        --n1; --n2;
        double x, y;
        scanf("%lf%lf", &x, &y);
        p[n1] = Point(x, y);
        scanf("%lf%lf", &x, &y);
        p[n2] = Point(x, y);
        double a = (pi - 2 * pi / n * (n2 - n1)) / 2;
        double l = abs(p[n2] - p[n1]) / 2 / cos(a);
        Vector v = -rotate(unit(p[n2] - p[n1]) * l, -a);
        Point o = p[n1] - v;
        rep(i,n) {
                p[(n1+i)%n] = o + v;
                v = rotate(v, -2 * pi / n);
        }
        rep(i,n) printf("%.6f %.6f
"
, p[i].X, p[i].Y); return 0; }

좋은 웹페이지 즐겨찾기