题目链接

http://acm.sgu.ru/problem.php?contest=0&problem=120

题目大意

将正n边形的顶点顺时针编号,给出任意两个顶点的坐标与编号,要求按编号顺序输出各顶点坐标。

题解

利用两个顶点的编号可以算出这两条半径的夹角,然后利用中点坐标和相似三角形算出中心坐标,最后使用向量旋转输出答案。

向量(x0,y0)顺时针旋转ta角:

x = cos(ta)*x0 + sin(ta)*y0

y = cos(ta)*y0 - sin(ta)*x0

代码

//
//  main.cpp
//  sgu
//
//  Site @haipz.com
//  Copyright (c) 2015年 林海鸿. All rights reserved.
//

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cfloat>
#include <map>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 150;
const double PI = acos(-1.0), eps = 1e-8;
struct Point {
    double x, y;
    Point() {}
    Point(double _x, double _y): x(_x), y(_y) {}
    void input() {
        scanf("%lf%lf", &x, &y);
        return;
    }
    void output() {
        printf("%f %f\n", x, y);
    }
    Point operator + (const Point &t) const {
        return Point(x + t.x, y + t.y);
    }
    Point operator - (const Point &t) const {
        return Point(x - t.x, y - t.y);
    }
    Point operator / (const double &t) const {
        return Point(x/t, y/t);
    }
};

Point f[N + 5];

int sgn(double a, double b) {
    if (fabs(a - b) <= eps) return 0;
    if (a > b) return 1;
    return -1;
}

double dis(Point a, Point b) {
    Point t = a - b;
    return sqrt(t.x*t.x + t.y*t.y);
}

Point Rotate(Point t, double deg) {
    double tx = cos(deg)*t.x + sin(deg)*t.y;
    double ty = cos(deg)*t.y - sin(deg)*t.x;
    return Point(tx, ty);
}

Point getCenter(int a, int b, int n) {
    double deg = PI/(double)n*(double)(b - a);
    double len = dis(f[a], f[b])/2.0/tan(deg);
    Point dir = Rotate(f[b] - f[a], PI/2.0);
    Point o = (f[a] + f[b])/2.0;
    o.x += dir.x/dis(Point(0, 0), dir)*len;
    o.y += dir.y/dis(Point(0, 0), dir)*len;
    return o;
}

int main() {
    int n, a, b;
    scanf("%d%d%d", &n, &a, &b);
    f[a].input();
    f[b].input();
    if (a > b) swap(a, b);
    Point o = getCenter(a, b, n);
    for (int i = 1; i < n; ++i) {
        int idx = (a + i - 1) % n + 1;
        double deg = PI*2.0/(double)n*(double)i;
        f[idx] = Rotate(f[a] - o, deg) + o;
    }
    for (int i = 1; i <= n; ++i) f[i].output();
    return 0;
}


转载保留版权:http://haipz.com/blog/i/6463 - 海胖博客