Timus #1444 – Pancake's Personal Website

题目说明：二维数组上有一些点，以第一个点为起点，把剩下的点连起来形成一个没有边相交的多边形，类似于一笔画，无需回到起点，只需把n个点连起来。

题目解析：类似于Timus #1607，极角排序，但排序顺序难想很多。首先找到x轴最小的点作为算法中整个图形的起点。计算每个点的atan2。对atan2进行升序排序，但是其中atan2角度可能相同，你可以画画图想想一下，对相同的距离也进行进行升序排序，距离越大连的越后面。但是我们这道题起点必须为输入的第一个点，这就意味着我们取x轴最小的点作为起的时候需要收尾也要相连，所以如果有大于两个的点位于x轴最小的点的正上方，就会出现收尾不可能相连的错误，这就需要对距离进行降序排序。具体sort函数排序方法可见代码f函数

Problem analysis English version:

Find the point with minimum x, exchange it to the first position.
Cal atan2.
Sort atan2 exclude the point with minimum x which is in the first position.
Find the index which is 1 and output the result.

Difference of sort definition between problem 1207:
Increasing order by theta. When theta is same, use increasing order of the distance from min_x point besides one situation. However if the points have same theta and is directly above the min_x point , we must use descending order of the distance from min_x point.

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;

struct point {
    int x, y, index;
    double theta;
} p[30000], temp;

int f(point& a, point& b) {
    if (a.theta == b.theta) {
        if (a.x == b.x && a.y > 0) return a.y * a.y > b.y * b.y;
        else return a.x * a.x + a.y * a.y < b.x* b.x + b.y * b.y;
    }
    return a.theta < b.theta;
}

int main() {
    int n;
    cin >> n;
    //input
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> p[i].x >> p[i].y;
        p[i].index = i + 1;
    }
    //exchange min_x to first position
    int min = p[0].x, minPosition = 0;
    for (int i = 1; i < n; i++) {
    	minPosition = min <= p[i].x ? minPosition : i;
    	min = min <= p[i].x ? min : p[i].x;
    }
    temp = p[0]; p[0] = p[minPosition]; p[minPosition] = temp;
    //cal atan2
    for (int i = 1; i < n; i++) {
        p[i].x -= p[0].x;
        p[i].y -= p[0].y;
        p[i].theta = atan2(p[i].y, p[i].x);
    }
    //sort exclude min_x
    sort(p + 1, p + n, f);
    //output
    cout << n << endl;
    for (int i = 0; i < n; i++) {
        if (p[i].index == 1) {
            for (int j = i; j < n; j++) cout << p[j].index << endl;
            for (int j = 0; j < i; j++) cout << p[j].index << endl;
            break;
        }
    }
}

#include<iostream>

#include<cmath>

#include<algorithm>

using namespace std;

struct point {

int x, y, index;

double theta;

} p[30000], temp;

int f(point& a, point& b) {

if (a.theta == b.theta) {

if (a.x == b.x && a.y > 0) return a.y * a.y > b.y * b.y;

else return a.x * a.x + a.y * a.y < b.x* b.x + b.y * b.y;

}

return a.theta < b.theta;

}

int main() {

int n;

cin >> n;

//input

for (int i = 0; i < n; i++) {

int x, y;

cin >> p[i].x >> p[i].y;

p[i].index = i + 1;

}

//exchange min_x to first position

int min = p[0].x, minPosition = 0;

for (int i = 1; i < n; i++) {

minPosition = min <= p[i].x ? minPosition : i;

min = min <= p[i].x ? min : p[i].x;

}

temp = p[0]; p[0] = p[minPosition]; p[minPosition] = temp;

//cal atan2

for (int i = 1; i < n; i++) {

p[i].x -= p[0].x;

p[i].y -= p[0].y;

p[i].theta = atan2(p[i].y, p[i].x);

}

//sort exclude min_x

sort(p + 1, p + n, f);

//output

cout << n << endl;

for (int i = 0; i < n; i++) {

if (p[i].index == 1) {

for (int j = i; j < n; j++) cout << p[j].index << endl;

for (int j = 0; j < i; j++) cout << p[j].index << endl;

break;

}

发表回复 取消回复

发表回复取消回复