poj 2007 Scrambled Polygon（凸多邊形頂點輸出）

描述：從(0，0)點開始輸入一個凸多邊形，這個凸多邊形，占有三個象限，按照逆時針的方式輸出各定點。

輸出例子：

Sample Input

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

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

思路：從上圖可以看出各象限都是斜率遞增方式，建立4個vector對應四個象限，然後分別將各象限的點存儲到相應的vector，最後對vector中的數據排序輸出。（思路比較水）

代碼：

[html] 
#include<iostream> 
#include<cstdio> 
#include<cmath> 
#include<vector> 
#include<algorithm> 
using namespace std; 
 
struct Vertice{ 
    int x,y; 
}; 
 
bool operator<(const Vertice &a, const Vertice &b) 
{     
    return atan2((double)a.y, (double)a.x)<atan2((double)b.y, (double)b.x); 
} 
 
int main() 
{ 
    Vertice point; 
    vector<Vertice> ivec[4]; 
    int i=0; 
    while(scanf("%d%d", &point.x, &point.y)!= EOF){ 
        //while(i++<10){ 
        //scanf("%d%d", &point.x, &point.y); 
        if(point.x>0&&point.y>0) 
            ivec[0].push_back(point); 
        else if(point.x<0&&point.y>0) 
            ivec[1].push_back(point); 
        else if(point.x<0&&point.y<0) 
            ivec[2].push_back(point); 
        else if(point.x>0&&point.y<0) 
            ivec[3].push_back(point); 
    } 
    for(int i=0;i<4;i++){ 
        if(ivec[i].size()!=0){ 
            sort(ivec[i].begin(),ivec[i].end()); 
        } 
    } 
 
    cout<<"(0,0)"<<endl; 
    int begin; 
    for(int i=0;i<4;i++){//找出凸邊形的起始點 
        if(ivec[i].size()==0){ 
            begin = (i+1)%4; 
            break; 
        } 
 
    } 
 
    for(int i=0;i<3;i++){ 
        int t = (begin+i)%4; 
        if(ivec[t].size()!=0){ 
            vector<Vertice>::iterator it; 
            for(it=ivec[t].begin();it!=ivec[t].end();it++){ 
                cout<<"("<<it->x<<","<<it->y<<")"<<endl; 
            } 
        } 
    } 
 
    system("pause"); 
    return 0; 
} 

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

struct Vertice{
 int x,y;
};

bool operator<(const Vertice &a, const Vertice &b)
{   
 return atan2((double)a.y, (double)a.x)<atan2((double)b.y, (double)b.x);
}

int main()
{
 Vertice point;
 vector<Vertice> ivec[4];
 int i=0;
 while(scanf("%d%d", &point.x, &point.y)!= EOF){
  //while(i++<10){
  //scanf("%d%d", &point.x, &point.y);
  if(point.x>0&&point.y>0)
   ivec[0].push_back(point);
  else if(point.x<0&&point.y>0)
   ivec[1].push_back(point);
  else if(point.x<0&&point.y<0)
   ivec[2].push_back(point);
  else if(point.x>0&&point.y<0)
   ivec[3].push_back(point);
 }
 for(int i=0;i<4;i++){
  if(ivec[i].size()!=0){
   sort(ivec[i].begin(),ivec[i].end());
  }
 }

 cout<<"(0,0)"<<endl;
 int begin;
 for(int i=0;i<4;i++){//找出凸邊形的起始點
  if(ivec[i].size()==0){
   begin = (i+1)%4;
   break;
  }

 }

 for(int i=0;i<3;i++){
  int t = (begin+i)%4;
  if(ivec[t].size()!=0){
   vector<Vertice>::iterator it;
   for(it=ivec[t].begin();it!=ivec[t].end();it++){
    cout<<"("<<it->x<<","<<it->y<<")"<<endl;
   }
  }
 }

 system("pause");
 return 0;
}
 

[html] 
View Code  
 
#include <iostream> 
#include <cstdlib> 
#include <cstring> 
#include <cstdio> 
#include <cmath> 
#include <algorithm> 
using namespace std; 
 
#define maxn 55 
#define pi acos(-1) 
 
struct Point 
{ 
    int x, y; 
} point[maxn]; 
 
bool operator <(const Point &a, const Point &b) 
{ 
    return atan2(a.y, a.x) < atan2(b.y, b.x); 
} 
 
double cal(double a) 
{ 
    if (a < 0) 
        return a + 2 * pi; 
    return a; 
} 
 
int main() 
{ 
    //freopen("t.txt", "r", stdin); 
    scanf("%d%d", &point[0].x, &point[0].y); 
    int n = 0; 
    while (scanf("%d%d", &point[n].x, &point[n].y) != EOF) 
        n++; 
    sort(point, point + n);//按照artan角度排序 
    double temp = 0; 
    point[n] = point[0]; 
    int s; 
    for (int i = 0; i < n; i++) 
    { 
        double a = cal(atan2(point[i + 1].y, point[i + 1].x) - atan2(point[i].y, point[i].x));//若前後兩點之間的角度相差最大，這裡就是凸邊形的起始位置 
        if (a > temp) 
        { 
            temp = a; 
            s = (i + 1) % n; 
        } 
    } 
    printf("(0,0)\n"); 
    for (int i = 0; i < n; i++) 
        printf("(%d,%d)\n", point[(s + i) % n].x, point[(s + i) % n].y); 
    return 0; 
} 

View Code

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

#define maxn 55
#define pi acos(-1)

struct Point
{
    int x, y;
} point[maxn];

bool operator <(const Point &a, const Point &b)
{
    return atan2(a.y, a.x) < atan2(b.y, b.x);
}

double cal(double a)
{
    if (a < 0)
        return a + 2 * pi;
    return a;
}

int main()
{
    //freopen("t.txt", "r", stdin);
    scanf("%d%d", &point[0].x, &point[0].y);
    int n = 0;
    while (scanf("%d%d", &point[n].x, &point[n].y) != EOF)
        n++;
    sort(point, point + n);//按照artan角度排序
    double temp = 0;
    point[n] = point[0];
    int s;
    for (int i = 0; i < n; i++)
    {
        double a = cal(atan2(point[i + 1].y, point[i + 1].x) - atan2(point[i].y, point[i].x));//若前後兩點之間的角度相差最大，這裡就是凸邊形的起始位置
        if (a > temp)
        {
            temp = a;
            s = (i + 1) % n;
        }
    }
    printf("(0,0)\n");
    for (int i = 0; i < n; i++)
        printf("(%d,%d)\n", point[(s + i) % n].x, point[(s + i) % n].y);
    return 0;
}