当前位置:编程学习 > C/C++ >>

圈地(斜率排序+坐标系旋转)

Problem 2 圈地(land.cpp/c/pas)
【题目描述】
2维平面上有n个木桩,你有一次圈地的机会并得到圈到的土地,为了体现你的高风亮节,你要使你圈到的土地面积尽量小。圈地需要圈一个至少3个点的多边形,多边形的顶点就是一个木桩,圈得的土地就是这个多边形内部的土地。
 
【输入格式】
第一行一个整数n,表示木桩个数。
  接下来n行,每行2个整数表示一个木桩的坐标,坐标两两不同。
【输出格式】
仅一行,表示最小圈得的土地面积,保留2位小数。
【样例输入】
样例1:
3
0 0
0 1
1 0
样例2:
4
0 0
0 1
0 2
1 1
【样例输出】
样例1:
0.50
样例2:
0.00
【数据范围】
    对于10%的数据,n<=100;
 对于30%的数据,n<=300;
 对于50%的数据,n<=500;
 对于100%的数据,n<=1000。
 
显然这题的多边形一定是三角形。
首先求出所有边,按k排序(必须先求出来,不能直接在排序的时候求)
然后考虑这些边,会发现正好是绕坐标系旋转一圈。
也就是说如果按照以这边为y轴从左至右排序,那么每转移一条边,只需要调换该边2个点的位置
这题没给范围,但是必须用long long
[cpp] 
#include<cstdio>  
#include<cstdlib>  
#include<cstring>  
#include<algorithm>  
#include<functional>  
#include<iostream>  
#include<cmath>  
using namespace std;  
#define MAXN (1000+10)  
#define INF (1000000000)  
#define eps 1e-10  
struct P  
{  
    int x,y;  
    long long operator*(const P &b)  
    {  
        return (long long)x*b.y-(long long)b.x*y;  
    }  
    friend bool operator<(P a,P b){if (a.x^b.x)  return a.x<b.x;return a.y<b.y;}  
}a[MAXN];  
long long abs2(long long x){if (x>0) return x;return -x;}  
int n,h[MAXN];  
struct E  
{  
    int i,j;  
    double k;  
    E(){}  
    E(int _i,int _j):i(_i),j(_j){if (a[i].x==a[j].x) k=1e10;else k=(double)(a[i].y-a[j].y)/(a[i].x-a[j].x);}  
    friend bool operator<(E a,E b){return a.k<b.k;    }  
}e[MAXN*MAXN/2];  
long long S2(P A,P B,P C)  
{  
    return abs2(A*B+B*C+C*A);  
}  
int size=0;  
int main()  
{  
    freopen("land.in","r",stdin);  
    freopen("land.out","w",stdout);  
    scanf("%d",&n);  
    for (int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);  
    long long ans=(long long)1<<60;  
    /*   
    for (int i=1;i<=n-2;i++) 
        for (int j=i+1;j<n;j++) 
            for (int k=j+1;k<=n;k++) 
                ans=min(ans,abs2(a[i]*a[j]+a[j]*a[k]+a[k]*a[i])); 
    */  
      
    sort(a+1,a+1+n);  
    for (int i=1;i<=n;i++) h[i]=i;  
    for (int i=1;i<n;i++)  
        for (int j=i+1;j<=n;j++)  
        {  
            e[++size]=E(i,j);             
        }  
      
    sort(e+1,e+1+size);  
      
    for (int i=1;i<=size&&ans;i++)  
    {  
        if (h[e[i].i]>1&&h[e[i].i]<n) ans=min(ans,S2(a[h[e[i].i]-1],a[h[e[i].i]],a[h[e[i].i]+1]));  
        if (h[e[i].j]>1&&h[e[i].j]<n) ans=min(ans,S2(a[h[e[i].j]-1],a[h[e[i].j]],a[h[e[i].j]+1]));  
        swap(a[h[e[i].i]],a[h[e[i].j]]);  
        swap(h[e[i].i],h[e[i].j]);  
    }  
      
    printf("%.2lf",(double)ans/2);  
    return 0;  
}  
 
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,