Codeforce 975E

标签: Codeforces  计算几何

E. Hag's Khashba
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Hag is a very talented person. He has always had an artist inside him but his father forced him to study mechanical engineering.

Yesterday he spent all of his time cutting a giant piece of wood trying to make it look like a goose. Anyway, his dad found out that he was doing arts rather than studying mechanics and other boring subjects. He confronted Hag with the fact that he is a spoiled son that does not care about his future, and if he continues to do arts he will cut his 25 Lira monthly allowance.

Hag is trying to prove to his dad that the wooden piece is a project for mechanics subject. He also told his dad that the wooden piece is a strictly convex polygon with nn vertices.

Hag brought two pins and pinned the polygon with them in the 11-st and 22-nd vertices to the wall. His dad has qq queries to Hag of two types.

  • 11 ff tt: pull a pin from the vertex ff, wait for the wooden polygon to rotate under the gravity force (if it will rotate) and stabilize. And then put the pin in vertex tt.
  • 22 vv: answer what are the coordinates of the vertex vv.

Please help Hag to answer his father's queries.

You can assume that the wood that forms the polygon has uniform density and the polygon has a positive thickness, same in all points. After every query of the 1-st type Hag's dad tries to move the polygon a bit and watches it stabilize again.

Input

The first line contains two integers nn and qq (3n100003≤n≤100001q2000001≤q≤200000) — the number of vertices in the polygon and the number of queries.

The next nn lines describe the wooden polygon, the ii-th line contains two integers xixi and yiyi (|xi|,|yi|108|xi|,|yi|≤108) — the coordinates of the ii-th vertex of the polygon. It is guaranteed that polygon is strictly convex and the vertices are given in the counter-clockwise order and all vertices are distinct.

The next qq lines describe the queries, one per line. Each query starts with its type 11 or 22. Each query of the first type continues with two integers ff and tt (1f,tn1≤f,t≤n) — the vertex the pin is taken from, and the vertex the pin is put to and the polygon finishes rotating. It is guaranteed that the vertex ff contains a pin. Each query of the second type continues with a single integer vv (1vn1≤v≤n) — the vertex the coordinates of which Hag should tell his father.

It is guaranteed that there is at least one query of the second type.

Output

The output should contain the answer to each query of second type — two numbers in a separate line. Your answer is considered correct, if its absolute or relative error does not exceed 10410−4.

Formally, let your answer be aa, and the jury's answer be bb. Your answer is considered correct if |ab|max(1,|b|)104|a−b|max(1,|b|)≤10−4

Examples
input
Copy
3 4
0 0
2 0
2 2
1 1 2
2 1
2 2
2 3
output
Copy
3.4142135624 -1.4142135624
2.0000000000 0.0000000000
0.5857864376 -1.4142135624
input
Copy
3 2
-1 1
0 0
1 1
1 1 2
2 1
output
Copy
1.0000000000 -1.0000000000
Note

In the first test note the initial and the final state of the wooden polygon.


Red Triangle is the initial state and the green one is the triangle after rotation around (2,0)(2,0).

In the second sample note that the polygon rotates 180180 degrees counter-clockwise or clockwise direction (it does not matter), because Hag's father makes sure that the polygon is stable and his son does not trick him.


题意:
一个n个点的凸包,一开始两个钉子钉在1号和2号点,给m种操作,第一类是将某个点上的钉子拔出,然后凸包由于重力作用绕一个点旋转,再将钉子插在另一个点上;第二类是询问某个点的坐标。

题解:

凸包的旋转依据是,最终状态是凸包的重心和旋转所绕的点在铅锤线上,这样可以求出重心旋转的角度,我们也可以理解为n个点反方向绕重心旋转了相同的角度。这样的好处是不用每转一次就更新n个点的坐标,而是只更新重心的真实坐标和总共的旋转角度,利用n个点与重心的相对位置不变就可算出n个点的真实位置了。

代码:

#include<bits/stdc++.h>
#define LL long long
#define N 10010
const double eps=1e-3;
using namespace std;
int dcmp(double x){if (fabs(x)<eps)return 0;else return x<0?-1:1;}
struct Point
{
    double x,y;
    Point(double x=0,double y=0):x(x),y(y){ }
    void read(){scanf("%lf%lf",&x,&y);}
};
typedef Point Vector;
Point a[N];
int g[N];

Vector operator + (Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);}
Vector operator - (Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}
Vector operator * (Vector a,double b){return Vector(a.x*b,a.y*b);}
Vector operator / (Vector a,double b){return Vector(a.x/b,a.y/b);}
double Dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}  //点积
double Length(Vector a){return sqrt(Dot(a,a));}
double Cross(Vector a,Vector b){return a.x*b.y-a.y*b.x;} //叉积
Vector Rotate(Vector a,double rad)// 向量 a 逆时针旋转 rad
{return Vector(a.x*cos(rad)-a.y*sin(rad),a.x*sin(rad)+a.y*cos(rad));}
Point Zhongxin(Point *a,int n)
{
    Point ans=Point(0,0);double ss=0;
    a[n]=a[0];
    for (int i=1;i<n-1;i++)
    {
        double s=fabs(Cross(a[i]-a[0],a[i+1]-a[0]));
        ans=ans+(a[0]+a[i]+a[i+1])*s/3;
        ss+=s;
    }
    if (dcmp(ss)==0) return Point(0,0);
    return ans/ss;
}

double GetAngle(Vector a)
{
    return atan2(a.x,a.y);
}

int main()
{
    int n,m;double ang=0; g[0]=g[1]=1; int a1=0,a2=1;
    scanf("%d%d",&n,&m);
    for (int i=0;i<n;i++) a[i].read();
    Point cc=Zhongxin(a,n);
    for (int i=0;i<n;i++) a[i]=a[i]-cc;
    for (int i=1;i<=m;i++)
    {
        int fg,j,k;
        scanf("%d%d",&fg,&j);
        if (fg&1)
        {
            scanf("%d",&k);j--;k--;
            g[j]--;
            if (!g[j])
            {
                int k=j==a1?a2:a1;
                Point t=cc+Rotate(a[k],ang);
                double r=GetAngle(t-cc);
                cc=t+Point(0,-1)*Length(a[k]);
                ang+=r;
            }
            if (j==a1) a1=k;else a2=k;
            g[k]++;
        }else
        {
            Point t=cc+Rotate(a[j-1],ang);
            double x=t.x,y=t.y;
            printf("%.8f %.8f\n",x,y);
        }
    }
}

版权声明:本文为nudt_spy原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/nudt_spy/article/details/80357103

智能推荐

CentOS学习之路1-wget下载安装配置

参考1: https://blog.csdn.net/zhaoyanjun6/article/details/79108129 参考2: http://www.souvc.com/?p=1569 CentOS学习之路1-wget下载安装配置 1.wget的安装与基本使用 安装wget yum 安装软件 默认安装保存在/var/cache/yum ,用于所有用户使用。 帮助命令 基本用法 例子:下载...

深入浅出Spring的IOC容器,对Spring的IOC容器源码进行深入理解

文章目录 DispatcherServlet整体继承图 入口:DispatcherServlet.init() HttpServletBean.init() FrameworkServlet.initServletBean() 首先大家,去看Spring的源码入口,第一个就是DispatcherServlet DispatcherServlet整体继承图 入口:DispatcherServlet....

laravel框架的课堂知识点概总

1. MVC 1.1 概念理解 MVC全名是Model View Controller,是模型(model)-视图(view)-控制器(controller)的缩写,一种软件设计典范,用一种业务逻辑、数据、界面显示分离的方法组织代码,将业务逻辑聚集到一个部件里面,在改进和个性化定制界面及用户交互的同时,不需要重新编写业务逻辑 MVC 是一种使用 MVC(Model View Controller ...

Unity人物角色动画系统学习总结

使用动画系统控制人物行走、转向、翻墙、滑行、拾取木头 混合树用来混合多个动画 MatchTarget用来匹配翻墙贴合墙上的某一点,人物以此为支点翻墙跳跃 IK动画类似于MatchTarget,控制两只手上的两个点来指定手的旋转和位置,使得拾取木头时更逼真 创建AnimatorController: 首先创建一个混合树,然后双击 可以看到该混合树有五种状态机,分别是Idle、WalkForward、...

Composer 安装 ThinkPHP6 问题

Composer 安装 ThinkPHP6 问题 先说说问题 一.运行环境要求 二.配置 参考: ThinkPHP6.0完全开发手册 先说说问题 执行ThinkPHP6的安装命令 遇到问题汇总如下: 看提示是要更新版本,执行命令更新。 更新之后,再次安装ThinkPHP,之后遇到如下问题。 尝试了很多方法,依然不能解决。其中包括使用https://packagist.phpcomposer.com...

猜你喜欢

Spring Boot 整合JDBC

今天主要讲解一下SpringBoot如何整合JDBC,没啥理论好说的,直接上代码,看项目整体结构 看一下对应的pom.xml 定义User.java 定义数据源配置,这里使用druid,所以需要写一个配置类 上面指定druid的属性配置,和用户登录的账号信息以及对应的过滤规则: 下面定义数据访问接口和对应的实现: 数据访问层很简单,直接注入JdbcTemplate模板即可,下面再看对应的servi...

html鼠标悬停显示样式

1.显示小手:     在style中添加cursor:pointer 实现鼠标悬停变成小手样式     实例:         其他参数: cursor语法: cursor : auto | crosshair | default | hand | move | help | wait | tex...

Yupoo(又拍网)的系统架构

Yupoo!(又拍网) 是目前国内最大的图片服务提供商,整个网站构建于大量的开源软件之上。以下为其使用到的开源软件信息: 操作系统:CentOS、MacOSX、Ubuntu 服务器:Apache、Nginx、Squid 数据库:MySQLmochiweb、MySQLdb 服务器监控:Cacti、Nagios、 开发语言:PHP、Python、Erlang、Java、Lua 分布式计算:Hadoop...

创建一个Servlet项目流程(入门)

版本 IDEA 2020.2 JDK1.8 apache-tomcat-9.0.36 项目流程 一、IDEA中新建JaveEE项目 项目起名,选择项目存放地址,点击finish创建成功 进入项目后,右键选择项目,选择add Framework Support 选择Web Application,点击OK 此时项目文件夹 在WEB-INF下创建两个目录classes和lib 按ctrl+alt+sh...

Docker部署SpringCloud ELK+RabbitMQ日志

Docker部署SpringCloud ELK+RabbitMQ日志  Im_Coder 原文:https://www.jianshu.com/p/f773f23096a9 一、效果图 image.png 二、ELK是什么? ELK由ElasticSearch、Logstash和Kiabana三个开源工具组成。 其中Elasticsearch是个开源分布式搜索引擎,它的特点有:分布式,索...