SGU120 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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
bzoj 2338: [HNOI2011] 직사각형(형상 계산)전송문 제목 대의: n개의 점을 제시하고 정점이 모두 n개의 점 중의 최대 직사각형을 구한다....
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.