poj 3348 Cows (叉积计算凸包面积)

2024-03-28 12:48

本文主要是介绍poj 3348 Cows (叉积计算凸包面积),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题意挺简单的,求凸包的面积然后除于50即可。

面积:固定某一点,找枚举凸包中的点,用叉积求即可:

#include <iostream>
#include <cstdio>
#include <cmath>
#include <stack>
#include <algorithm>
#define PI acos(-1)
#define MAXN 1000+10
using namespace std;int N,L;struct point{int x,y;
}p[MAXN];
int cross(int x1,int y1,int x2,int y2){return x2*y1 - x1*y2;
}
double dis(const point &a,const point &b){return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
double dis(int x1,int y1,int x2,int y2){return sqrt((x1 - x2)*(x1 - x2) + (y1 - y2) * (y1 - y2));
}
bool cmp(const point &a,const point &b){int x1 = a.x - p[0].x,y1 = a.y - p[0].y;int x2 = b.x - p[0].x,y2 = b.y - p[0].y;if(cross(x1,y1,x2,y2) != 0)return cross(x1,y1,x2,y2) < 0;elsereturn dis(a,p[0]) < dis(b,p[0]);
}
bool ok(point p1,point p2,point p3){int x1 = p2.x - p1.x;int y1 = p2.y - p1.y;int x2 = p3.x - p2.x;int y2 = p3.y - p2.y;int c = cross(x1,y1,x2,y2);if(c <= 0) return true;else return false;
}
//凸包扫描算法
void GrahamScan(){stack<point> s;s.push(p[0]);s.push(p[1]);int i = 2;while(i < N ){point p2 = s.top();s.pop();point p1 = s.top();point p3 = p[i];if(ok(p1,p2,p3)){s.push(p2);s.push(p[i]);i++;}}s.pop();double S = 0.0;point pfa = p[N-1];point p1 = s.top();s.pop();while(!s.empty()){point p2 = s.top();s.pop();S += abs(cross(p1.x - pfa.x,p1.y - pfa.y,p2.x - pfa.x,p2.y-pfa.y)/2.0);p1 = p2;}printf("%d\n",(int)(S/50));
}int main()
{while(~scanf("%d",&N)){int m = 1;scanf("%d%d",&p[0].x,&p[0].y);for(int i=1;i<N;i++){point pt;scanf("%d%d",&pt.x,&pt.y);if(pt.y < p[0].y || (pt.y == p[0].y && pt.x < p[0].x)){p[m].x = p[0].x;p[m++].y = p[0].y;p[0].x = pt.x;p[0].y = pt.y;}else{p[m].x = pt.x;p[m++].y = pt.y;}}sort(p+1,p+N,cmp);GrahamScan();}return 0;
}


这篇关于poj 3348 Cows (叉积计算凸包面积)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/855660

相关文章

Python并行处理实战之如何使用ProcessPoolExecutor加速计算

《Python并行处理实战之如何使用ProcessPoolExecutor加速计算》Python提供了多种并行处理的方式,其中concurrent.futures模块的ProcessPoolExecu... 目录简介完整代码示例代码解释1. 导入必要的模块2. 定义处理函数3. 主函数4. 生成数字列表5.

Java计算经纬度距离的示例代码

《Java计算经纬度距离的示例代码》在Java中计算两个经纬度之间的距离,可以使用多种方法(代码示例均返回米为单位),文中整理了常用的5种方法,感兴趣的小伙伴可以了解一下... 目录1. Haversine公式(中等精度,推荐通用场景)2. 球面余弦定理(简单但精度较低)3. Vincenty公式(高精度,

windows和Linux使用命令行计算文件的MD5值

《windows和Linux使用命令行计算文件的MD5值》在Windows和Linux系统中,您可以使用命令行(终端或命令提示符)来计算文件的MD5值,文章介绍了在Windows和Linux/macO... 目录在Windows上:在linux或MACOS上:总结在Windows上:可以使用certuti

Python如何计算两个不同类型列表的相似度

《Python如何计算两个不同类型列表的相似度》在编程中,经常需要比较两个列表的相似度,尤其是当这两个列表包含不同类型的元素时,下面小编就来讲讲如何使用Python计算两个不同类型列表的相似度吧... 目录摘要引言数字类型相似度欧几里得距离曼哈顿距离字符串类型相似度Levenshtein距离Jaccard相

使用C#代码计算数学表达式实例

《使用C#代码计算数学表达式实例》这段文字主要讲述了如何使用C#语言来计算数学表达式,该程序通过使用Dictionary保存变量,定义了运算符优先级,并实现了EvaluateExpression方法来... 目录C#代码计算数学表达式该方法很长,因此我将分段描述下面的代码片段显示了下一步以下代码显示该方法如

如何用Java结合经纬度位置计算目标点的日出日落时间详解

《如何用Java结合经纬度位置计算目标点的日出日落时间详解》这篇文章主详细讲解了如何基于目标点的经纬度计算日出日落时间,提供了在线API和Java库两种计算方法,并通过实际案例展示了其应用,需要的朋友... 目录前言一、应用示例1、天安门升旗时间2、湖南省日出日落信息二、Java日出日落计算1、在线API2

usaco 1.2 Milking Cows(类hash表)

第一种思路被卡了时间 到第二种思路的时候就觉得第一种思路太坑爹了 代码又长又臭还超时!! 第一种思路:我不知道为什么最后一组数据会被卡 超时超了0.2s左右 大概想法是 快排加一个遍历 先将开始时间按升序排好 然后开始遍历比较 1 若 下一个开始beg[i] 小于 tem_end 则说明本组数据与上组数据是在连续的一个区间 取max( ed[i],tem_end ) 2 反之 这个

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码: #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s

poj 1511 Invitation Cards(spfa最短路)

题意是给你点与点之间的距离,求来回到点1的最短路中的边权和。 因为边很大,不能用原来的dijkstra什么的,所以用spfa来做。并且注意要用long long int 来存储。 稍微改了一下学长的模板。 stack stl 实现代码: #include<stdio.h>#include<stack>using namespace std;const int M