L3-021 神坛极角排序

朱雀 2022-03-11 00:59 169阅读 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 条评论，169人围观）

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

相关阅读

相关荷尖角:希尔排序

package D_common; import java.util.Scanner; public class 希尔排序 {

r囧r小猫/ 2024年03月31日 11:48/ 0 赞/ 60 阅读

相关荷尖角:快速排序

package D_common; import java.util.Scanner; public class 快速排序 {

￡神魔★判官ぃ/ 2024年03月31日 11:48/ 0 赞/ 61 阅读

相关 L3-021 神坛

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

女爷i/ 2023年09月26日 18:27/ 0 赞/ 7 阅读

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

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

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

相关 ecnu 3059. 极坐标排序

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

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

相关 L3-021 神坛极角排序

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

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

相关走下神坛吧，算法！

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

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

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

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

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

相关极角排序

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

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

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

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

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