题目链接: https://vjudge.net/problem/POJ-3348
题意: 转换题意后即是求凸包的面积.
思路:
套模板, 求凸包面积即转换为多个三角形面积之和, 用叉积求, 然后除 2, 因为本题除 50, 所以最后除 100.
- AC code:
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- #include<cmath>
- using namespace std;
- const int maxn=10005;
- const double PI=acos(-1.0);
- struct Point{
- int x,y;
- Point():x(0),y(0){}
- Point(int x,int y):x(x),y(y){}
- }list[maxn];
- int stack[maxn],top;
- // 计算叉积 p0p1*p0p2
- int cross(Point p0,Point p1,Point p2){
- return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
- }
- // 计算 p1p2 的距离
- double dis(Point p1,Point p2){
- return sqrt((double)(p2.x-p1.x)*(p2.x-p1.x)+(p2.y-p1.y)*(p2.y-p1.y));
- }
- // 极角排序函数, 角度相同则距离小的在前面
- bool cmp(Point p1,Point p2){
- int tmp=cross(list[0],p1,p2);
- if(tmp>0) return true;
- else if(tmp==0&&dis(list[0],p1)<dis(list[0],p2)) return true;
- else return false;
- }
- // 输入, 把最左下角放在 list[0], 并且进行极角排序
- void init(int n){
- Point p0;
- scanf("%d%d",&list[0].x,&list[0].y);
- p0.x=list[0].x;
- p0.y=list[0].y;
- int k=0;
- for(int i=1;i<n;++i){
- scanf("%d%d",&list[i].x,&list[i].y);
- if((p0.y>list[i].y)||((p0.y==list[i].y)&&(p0.x>list[i].x))){
- p0.x=list[i].x;
- p0.y=list[i].y;
- k=i;
- }
- }
- list[k]=list[0];
- list[0]=p0;
- sort(list+1,list+n,cmp);
- }
- //graham 扫描法求凸包, 凸包顶点存在 stack 栈中
- // 从栈底到栈顶一次是逆时针方向排列的
- // 如果要求凸包的一条边有 2 个以上的点
- // 那么要将 while 中的 <= 改成 <// 但这不能将最后一条边上的多个点保留
- // 因为排序时将距离近的点排在前面
- // 那么最后一条边上的点仅有距离最远的会被保留, 其余的会被出栈
- // 所以最后一条边需要特判
- void graham(int n){
- if(n==1){
- top=0;
- stack[0]=0;
- return;
- }
- top=1;
- stack[0]=0;
- stack[1]=1;
- for(int i=2;i<n;++i){
- while(top>0&&cross(list[stack[top-1]],list[stack[top]],list[i])<=0) --top;
- stack[++top]=i;
- }
- }
- int n,ans;
- int main(){
- while(~scanf("%d",&n)){
- ans=0;
- init(n);
- graham(n);
- for(int i=0;i<top;++i)
- ans+=cross(Point(0,0),list[stack[i]],list[stack[i+1]]);
- ans+=cross(Point(0,0),list[stack[top]],list[stack[0]]);
- printf("%d\n",ans/100);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3280466.html