L3-021 神坛极角排序

朱雀 2022-03-11 00:59 161阅读 0赞

L3-021 神坛 （30 分）

在古老的迈瑞城，巍然屹立着 n 块神石。长老们商议，选取 3 块神石围成一个神坛。因为神坛的能量强度与它的面积成反比，因此神坛的面积越小越好。特殊地，如果有两块神石坐标相同，或者三块神石共线，神坛的面积为 `0.000`。

长老们发现这个问题没有那么简单，于是委托你编程解决这个难题。

### 输入格式： ###

输入在第一行给出一个正整数 n（3 ≤ n ≤ 5000）。随后 n 行，每行有两个整数，分别表示神石的横坐标、纵坐标（−109≤ 横坐标、纵坐标 <109）。

### 输出格式： ###

在一行中输出神坛的最小面积，四舍五入保留 3 位小数。

### 输入样例： ###

8
    3 4
    2 4
    1 1
    4 1
    0 3
    3 0
    1 3
    4 2

### 输出样例： ###

0.500

极角排序求面积

#include<stdio.h>
    #include<string.h>
    #include<math.h>
    #include<iostream>
    #include<string>
    #include<algorithm>
    #include<map>
    #include<set>
    #include<queue>
    #include<stack>
    #include<vector>
    using namespace std;
    #define inf 0x3f3f3f3f
    #define LL long long
    
    struct lzy
    {
    	LL x,y;
    }d[5005],vec[5005];
    bool cmp(lzy a,lzy b)
    {
    	return a.x*b.y<a.y*b.x;
    }
    int main()
    {
    	int n,i,j;
    	double area=1e18;
    	scanf("%d",&n);
    	for(i=1;i<=n;i++)
    		scanf("%lld%lld",&d[i].x,&d[i].y);
    	for(i=1;i<=n;i++)
    	{
    		int tot=0;
    		for(j=1;j<=n;j++)
    		{
    			if(i==j)continue;
    			vec[tot].x=d[j].x-d[i].x;
    			vec[tot++].y=d[j].y-d[i].y;
    		}
    		sort(vec,vec+tot,cmp);
    		for(j=1;j<tot;j++)
    		{
    			area=min(area,1.*abs(vec[j].x*vec[j-1].y-vec[j].y*vec[j-1].x));
    		}
    	}
    	printf("%.3f\n",area*0.5);
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，161人围观）

还没有评论，来说两句吧...

相关阅读

相关归并排序详解（效率极高）

归并排序介绍归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divid

╰+攻爆jí腚メ/ 2023年07月08日 05:49/ 0 赞/ 42 阅读

相关 ecnu 3059. 极坐标排序

[题目][Link 1] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9

淡淡的烟草味﹌/ 2022年10月06日 00:56/ 0 赞/ 129 阅读

相关【学生信息管理系统】实时错误'3021' BOF EOF

在使用“修改”功能中的“删除记录”功能，以“修改学籍信息”为例，如下图 ![SouthEast][] 在删除记录的时候，把全部的记录都删除之后会报

Dear 丶/ 2022年07月24日 05:24/ 0 赞/ 182 阅读

相关学生信息系统优化（二）---实时错误"3021"

背景当我让师傅给我初次验项目时，师傅就“兴致勃勃”的给我展示了这个错误。当将信息全部删除时，3021就蹦了出来。我一脸懵逼，师傅们说这是他们也遇到过的错误。果然在通往成功的

我就是我/ 2022年05月18日 06:42/ 0 赞/ 289 阅读

相关 L1-034 点赞 (map排序)

L1-034 点赞（20 分）微博上有个“点赞”功能，你可以为你喜欢的博文点个赞表示支持。每篇博文都有一些刻画其特性的标签，而你点赞的博文的类型，也间接刻画了你的特性。本

た入场券/ 2022年03月16日 01:24/ 0 赞/ 162 阅读

相关 L3-021 神坛极角排序

L3-021 神坛（30 分）在古老的迈瑞城，巍然屹立着 n 块神石。长老们商议，选取 3 块神石围成一个神坛。因为神坛的能量强度与它的面积成反比，因此神坛的面积越小越好

朱雀/ 2022年03月11日 00:59/ 0 赞/ 162 阅读

相关走下神坛吧，算法！

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg] 作者 | 周林来源 | Java之猿程之家引言在互联网、

ゞ浴缸里的玫瑰/ 2022年02月23日 02:34/ 0 赞/ 219 阅读

相关 poj 1696 极角排序（解题报告）

include<iostream> include<cmath> include<algorithm> using namespace std;

浅浅的花香味﹌/ 2021年11月01日 13:16/ 0 赞/ 325 阅读

相关极角排序

//若干个点的极角排序 POJ2007 Scrambled Polygon include<iostream> include<cstdio> in

一时失言乱红尘/ 2021年09月29日 15:30/ 0 赞/ 270 阅读

相关快速排序---效率极高

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

雨点打透心脏的1/2处/ 2021年09月24日 01:04/ 0 赞/ 277 阅读