2020ICPC昆明站——J.Mr. Main and Windmills(计算几何)

简介: 2020ICPC昆明站——J.Mr. Main and Windmills(计算几何)

原题链接

题意:

车从( s x , s y )开往( e x , e y ),在车的同一侧有n个风车,q次询问,每次询问第h个点对于其他点的位置变化的第k次的点。

思路:

题意有点抽象,模拟一下样例就很好懂了。

20200401134307494.png第二个样例问的是3号点第二个变化的位置点。

从s ss向e ee走,当车在[ s , A ]区间时,在车的视角看,1 , 2 , 4都在3的左边。

当车在[ A , B ]区间时,4变成了在3的右边,而1 , 2都在3的左边,所以第一个变化的点是4,第一个变化的位置是A.

当车在[ B , C ]区间时,2也变成了在3的右边,这时候2 , 4都在3 的右边,1在3的左边,所以第二个变化的点是2,第二个变化的位置是B.

当车在[ C , + 00 ]区间时,1也变成了在3的右边,这时候1 , 2 , 4都在3的右边,所以第三个变化的点是1,第二个变化的位置是C.

思路就是求每个点跟询问点所组成的直线和直线( s , e )的交点,按照交点到起点s的距离从小到大排序,第k个的交点坐标就是答案。

要注意只有交点在[ s , e ]时才是有效的。

运气比较好,找的板子没有被卡精度。

代码:

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PLL;
typedef pair<int, int>PII;
typedef pair<double, double>PDD;
#define I_int ll
inline ll read()
{
    ll x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
#define read read()
#define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define multiCase int T;cin>>T;for(int t=1;t<=T;t++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i<(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define perr(i,a,b) for(int i=(a);i>(b);i--)
ll ksm(ll a, ll b, ll p)
{
    ll res = 1;
    while(b)
    {
        if(b & 1)res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}
const int inf = 0x3f3f3f3f;
#define PI acos(-1)
const double eps = 1e-8;
const int maxn=1e6+100;
int n,m;
const double epsi=1e-10;
struct Point
{
  double x,y;
  Point(double _x=0,double _y=0):x(_x),y(_y){}
  Point operator -(const Point &op) const
  {
    return Point(x-op.x,y-op.y);
  }
  double operator ^(const Point &op) const
  {
    return x*op.y-y*op.x;
  }
};
inline int sign(const double &x)
{
  if(x>epsi) return 1;
  if(x<-epsi) return -1;
  return 0;
}
inline double sqr( const double &x)
{
  return x*x;
}
inline double dis(const Point &p1,const Point &p2)
{
  return sqrt(sqr(p1.x-p2.x)+sqr(p1.y-p2.y));
}
inline double mul(const Point &p0,const Point &p1,const Point &p2)
{
  return (p1-p0)^(p2-p0);
}
inline int cross(const Point &p1,const Point &p2,const Point &p3,const Point &p4,Point &p)
{
  double a1=mul(p1,p2,p3),a2=mul(p1,p2,p4);
  if(sign(a1)==0&&sign(a2)==0) return 2;//重叠
  if(sign(a1-a2)==0) return 0;//平行
  p.x=(a2*p3.x-a1*p4.x)/(a2-a1);
  p.y=(a2*p3.y-a1*p4.y)/(a2-a1);
  return 1;//相交
}
Point a[1100],s,e;
struct node{
    double x,y,d;
}b[1100];
bool cmp(node a,node b){
    return a.d<b.d;
}
int main()
{
    n=read,m=read;
    scanf("%lf%lf%lf%lf",&s.x,&s.y,&e.x,&e.y);
    rep(i,1,n){
        scanf("%lf%lf",&a[i].x,&a[i].y);
    }
    double FUCK=dis(s,e);
    rep(i,1,m){
        int idx=0,h=read,k=read;
        rep(j,1,n){
            if(j==h) continue;
            Point t;
            int flag=cross(a[h],a[j],s,e,t);
            if(flag&&dis(t,s)<=FUCK&&dis(t,e)<=FUCK){
                b[++idx]={t.x,t.y,dis(t,s)};
            }
        }
        ///cout<<i<<"*******"<<idx<<endl;
        if(idx<k) puts("-1");
        else{
            sort(b+1,b+1+idx,cmp);
            printf("%.10lf %.10lf\n",b[k].x,b[k].y);
        }
    }
    return 0;
}
目录
相关文章
|
5月前
|
机器学习/深度学习 算法 数据挖掘
【2024 华数杯 国际数学建模竞赛】B题 Photovoltaic Power光伏发电 34页论文及python 代码
本文通过建立数学模型和应用多种数据分析方法,研究了中国电力供应与光伏发电的发展趋势、光伏电站建设的可行性、中国光伏发电的最大潜力、清洁能源替代燃煤发电的可能性,以及光伏发电在实现国家碳中和战略目标中的作用,并提出了相关政策建议。
94 4
【2024 华数杯 国际数学建模竞赛】B题 Photovoltaic Power光伏发电 34页论文及python 代码
|
5月前
|
算法 搜索推荐 数据挖掘
【2024年华数杯全国大学生数学建模竞赛】C题:老外游中国 问题思路分析及Python代码实现
本文提供了2024年华数杯全国大学生数学建模竞赛C题“老外游中国”的解题思路分析和Python代码实现,涉及景点评分统计、城市综合评价、游玩路线规划以及特定条件下的旅游优化问题。
716 6
【2024年华数杯全国大学生数学建模竞赛】C题:老外游中国 问题思路分析及Python代码实现
|
8月前
|
Go 数据库 知识图谱
中科院一区7.9分top刊|好久不见,网络药理学(实验为主生信为辅)
`Phytomedicine` 杂志2023年6月发表了一篇关于网络药理学的文章,研究了肾康注射液(SKI)治疗糖尿病肾病(DKD)的机制,重点关注其通过Keap1/Nrf2/Ho-1信号通路对抗氧化应激的影响。研究表明,SKI可能通过调节氧化还原相关信号,减轻AGEs诱导的氧化应激,从而改善DKD。在动物实验中,SKI降低了DKD大鼠的尿蛋白、Scr水平,改善了肾功能和血脂,减少了氧化应激指标,并在细胞实验中显示了类似的效果,激活了Keap1/Nrf2/Ho-1通路。
244 1
|
8月前
|
人工智能 测试技术
【“红旗杯”第十四届吉林省大学生程序设计竞赛】 之 C - String Game
【“红旗杯”第十四届吉林省大学生程序设计竞赛】 之 C - String Game
|
8月前
|
C++
【PTA】​L1-079 天梯赛的善良​ (C++)
【PTA】​L1-079 天梯赛的善良​ (C++)
120 0
【PTA】​L1-079 天梯赛的善良​ (C++)
|
8月前
(2021 ICPC)亚洲区域赛(昆明)I.Mr. Main and Windmills
(2021 ICPC)亚洲区域赛(昆明)I.Mr. Main and Windmills
42 0
(2021 ICPC)亚洲区域赛(昆明)I.Mr. Main and Windmills
|
Python
2020 华数杯——脱贫帮扶绩效评价(Python代码实现)
2020 华数杯——脱贫帮扶绩效评价(Python代码实现)
128 0
|
Java 测试技术 API
满地坑!细数List的10个坑
今天我们主要来说一说List操作在实际使用中有哪些坑,以及面对这些坑的时候我们要怎么解决。

热门文章

最新文章