URAL 1207 Median on the Plane(直线分割点集:极角排序)
http://acm.timus.ru/problem.aspx?space=1&num=1207
题意:
给你n个点的点集,任意3点不共线. 要你找出其中两点,使得该两点的连线正好二等分了整个点集.
分析:
只要找到该点集的最左下角的点(优先x坐标最小,如果有多个x坐标最小的点,那就选那个y坐标小的点.不可能两点重合)
找到该点之后,把所有其他点与该点连线,按连线的极角排序即可.最终输出该点和排序后数组的中间那个点即可.
极角排序我们不是直接算极角的,而是用两个向量的叉积的正负来判断到底是第一个向量在左边还是第二个向量在左边. 在左边的向量的端点在数组的前面.
AC代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=10000+5;
const double eps=1e-10;
int dcmp(double x)
{
if(fabs(x)<eps) return 0;
return x<0?-1:1;
}
struct Point
{
double x,y;
int id;
Point(){}
Point(double x,double y,int id):x(x),y(y),id(id){}
}P[maxn];
typedef Point Vector;
Vector operator-(Point A,Point B)
{
return Vector(A.x-B.x,A.y-B.y,0);
}
double Cross(Vector A,Vector B)
{
return A.x*B.y-A.y*B.x;
}
bool cmp(Point A,Point B)//极角排序比较函数
{
return dcmp(Cross(A-P[0],B-P[0]))<0;
}
int main()
{
int n;
while(scanf("%d",&n)==1)
{
scanf("%lf%lf",&P[0].x,&P[0].y);
P[0].id=1;
for(int i=1;i<n;++i)
{
scanf("%lf%lf",&P[i].x,&P[i].y);
P[i].id=i+1;
if(P[i].x<P[0].x || (P[i].x==P[0].x && P[i].y<P[0].y) )
swap(P[0],P[i]);//将最左下角的点换到0号位置
}
sort(P+1,P+n,cmp);
printf("%d %d\n",P[0].id,P[n/2].id);
}
return 0;
}
分享到:
相关推荐
Ural解题思路 Ural解题思路 Ural解题思路 Ural解题思路
Ural
URAL(Timus Online Judge)部分测试数据 不全
URAL3D
Pascal acm_timus_ural_1148.pas
俄罗斯URAL联邦大学Online Judge Aizu : 日本会津大学Online Judge SPOJ : SPOJ是波兰最为出色的Online Judge之一 , 界面和谐题目类型也非常丰富 , 适合有一定基础的选手练习 , 对高手而言也是个提高能力的良好平台 ...
28. The Theoretical Background of the Ural-Altale Hypothesis The hypothesis of common origin of the Altaic languages,and even the Ural-Altaic languages,dates from the first half of the last century....
Thanks to the National Nat- ural Science Foundation (61033013, 60775045, 61672364, 61672365), Soochow scholar program (14317360, 58320007) and the key subjects of Jiangsu province “Technology of ...
Ural 1238 源代码 涉及算法(动态规划、贪心、DFS)
ural 题解 yuhch123。 关于yuhch123: ioi2008 金牌第一名,这是当初它做ural 第一卷时的题解
Pascal acm_timus_ural_1099.pas
Ural ACM 1000源代码(c++),vc++6.0在XPsp2下编译通过,Timus Online Judge再线测评通过
Philip_Dural_UX-UI_Designer:UXUI设计器配置文件
The continent is surrounded by the Mediterranean Sea to the north, both the Suez Canal and the Red Sea along the Sinai Peninsula to the northeast, the Indian Ocean to the southeast, and the Atlantic ...
包含了ural题库中Vol_I 到Vol_III的所有题目的解题思路
部分题解 大牛出品 Vol1-3 不是很全,约有200题左右
URAL-PHA
资源分类:Python库 所属语言:Python 资源全名:ural-0.28.0.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
因为大三了 不弄ACM了 所以这些就删了 删之前希望可以帮到别人
Mainly based on black box compo2 nent met hod , t he development of optical and st ruct ural design sof tware is completed using VC + + language. The integration and link of sof tware and AutoCAD/ ...