阿生的粉丝团

正文索引 [隐藏]

题目描述:

夭折了,阿生竟然有粉丝团了,而且还是清一色的妹子。激动的阿生忍不住咬了自己一下,确定一下不是梦,好吧,还真是个梦。醒来的阿生悲痛欲绝,只想知道梦境中她们平面坐标的逆时针排列,你能帮帮他吗。

输入描述:

输入每行给出一组整数x,y代表梦境中阿生粉丝的平面坐标,并且保证第一个的坐标永远是(0 0): -1000= x <= 1000, -1000<= y <= 1000

输出描述:

按照(%d,%d)的格式输出即可。

输入样例:

0 0
70 -50
60 30
-30 -50
80 20
50 -60
90 -20
-30 -40
-10 -60
90 10

输出样例:

(0,0)
(-30,-40)
(-30,-50)
(-10,-60)
(50,-60)
(70,-50)
(90,-20)
(90,10)
(80,20)
(60,30)

解题思路:

这题的本质是结构体排序,先输出原点(0,0),然后从第三象限开始逆时针旋转,若是不同象限的坐标按照三四一二象限的顺序来排序,若是同一象限的坐标则按照y/x的大小来升序排列,最后输出即可。

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define Up(i,a,b) for(int i = a; i <= b; i++)

struct dot
{
    int x,y;
    int level;   //象限,第三象限1,第四象限2,第一象限3,第二象限4
};

bool cmp(dot d1,dot d2)
{
    if(d1.level != d2.level)
    {
        return d1.level < d2.level;
    }
    else
    {
        double _1 = d1.y*1.0/d1.x;
        double _2 = d2.y*1.0/d2.x;
        return _1 < _2;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    vector<dot> v;
    int x,y;
    while(cin >> x >> y)
    {
        if(x && y)  //(0,0)除外
        {
            int level;
            if(x>0 && y>0)    //第一象限
            {
                level = 3;
            }
            else if(x>0 && y<0)    //第四象限
            {
                level = 2;
            }
            else if(x<0 && y<0)    //第三象限
            {
                level = 1;
            }
            else //x<0 && y>0     //第二象限
            {
                level = 4;
            }
            v.push_back({x,y,level});
        }
        //if(x==90 && y == 10) break;   //测试样例的时候用
    }
    sort(v.begin(),v.end(),cmp);
    cout << "(0,0)" << endl;
    for(auto it : v)
    {
        printf("(%d,%d)\n",it.x,it.y);
    }
    return 0;
}

来自生哥的官方题解:

生哥太强了,代码简洁精练,我还没开始main函数,生哥就已经AC了。赞一个

#include <bits/stdc++.h>
using namespace std;
struct p{
    int x,y;
    p():x(0),y(0) {}
    p(int x,int y)
    {
        this->x = x;
        this->y = y;
    }
}ls[10001];
bool cmp(p a,p b){
    return a.x*b.y - a.y*b.x>0;
}
int main(){
    int x,y,n = 0;
    while(cin>>x>>y){
        ls[n++]=p(x,y);
        if(x==90&&y==10) break;
    }
    sort(ls,ls+n,cmp);
    for(int i = 0;i<n;++i){
        cout<<"("<<ls[i].x<<","<<ls[i].y<<")"<<endl;
    }
    return 0;
}