首页 > 其他分享 >P4468[SCOI2007]折纸-题解

P4468[SCOI2007]折纸-题解

时间:2024-07-29 10:32:55浏览次数:12  
标签:now p1 return point 题解 ans 折纸 l1 SCOI2007

题意:

有一个左下角为 \((0,0)\),右上角为 \((100,100)\) 的正方形,给你 \(n\) 个有向线段和 \(m\) 个询问,将纸片依次按直线折叠,然后每次询问让你求出某个点上有多少层纸。

分析:

观察到数据范围非常小,于是可以直接对于每个询问 \(\mathcal{O}(2^n)\) 来求。

具体的,对于每一个点,倒着枚举 \(n\) 条直线。

如果这个点在直线的左边,那么就继续递归这个点和这个点关于直线的对称点;如果在右边,那么这个点就不在纸上,直接结束递归。

最后只需要看有多少个点在 \((0,0)\) 到 \((100,100)\) 内即可。

而在代码中,我用的是 \(y=kx+b\) 的形式来表示一条直线,这样子要求对称的话就只需要根据垂直的线 \(k\) 相乘为 \(-1\),就可以求出垂足,然后再求对称即可。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define ll long long
using namespace std;
const int N = 55;
const double eps = 1e-6;
int n,m,ans;
struct point
{
    double x,y;
    friend point operator-(point x,point y){return {x.x-y.x,x.y-y.y};}
    friend double operator*(point x,point y){return x.x*y.y-x.y*y.x;}
}p[N][2];
struct line{double k,b;}l[N];
line f(point p1,point p2)//将用两个点表示直线转化为用y=kx+b表示的形式
{
    if(p1.x == p2.x)return {1e9,p1.x};
    line ans;
    ans.k = (p1.y-p2.y)/(p1.x-p2.x);
    ans.b = p1.y-ans.k*p1.x;
    return ans;
}
point jiao(line l1,line l2)//求两直线的交点
{
    point ans;ans.x = (l2.b-l1.b)/(l1.k-l2.k);
    ans.y = l1.k*ans.x+l1.b;
    return ans;
}
point chuizu(point p1,line l1)//求垂足
{
    if(fabs(l1.k) < eps)return {p1.x,l1.b};
    if(l1.k == 1e9)return {l1.b,p1.y};
    line l2;l2.k = -1/l1.k;l2.b = p1.y-l2.k*p1.x;
    return jiao(l1,l2);
}
point mirror(point p1,point p2){return {p2.x*2-p1.x,p2.y*2-p1.y};}//对称点
bool pd(point now,point x,point y){return (y-x)*(now-x) > eps;}//用叉积判断一个点是否在直线左边
bool check(point now){return now.x > eps&&now.x < 100-eps&&now.y > eps&& now.y < 100-eps;}//判断点是否在原正方形内

void dfs(int x,point now)
{
    if(!x)return (void)(ans += check(now));
    point nex = mirror(now,chuizu(now,l[x]));
    if(pd(now,p[x][0],p[x][1]))dfs(x-1,now),dfs(x-1,nex);
}
inline double rd(){double x;scanf("%lf",&x);return x;}
int main()
{
    n = rd();
    for(int i = 1;i <= n;i++)
    {
        p[i][0] = {rd(),rd()};p[i][1] = {rd(),rd()};
        l[i] = f(p[i][0],p[i][1]);
    }
    m = rd();
    while(m--)
    {
        point x = {rd(),rd()};ans = 0;
        dfs(n,x);
        printf("%d\n",ans);
    }
    return 0;
}

标签:now,p1,return,point,题解,ans,折纸,l1,SCOI2007
From: https://www.cnblogs.com/max0810/p/18329537

相关文章

  • P8540 「Wdoi-2」夜空中的 UFO 恋曲 题解
    hanghangakioi考试的时候在乱猜结论,交了几遍就过了,证明当然是赛后才想的()文中加粗部分是需要读者稍微思考一下原因的地方(不是重点)。先考虑一下样例二,将\(10^{18}\)化成二进制:\(1101...001000000000000000000\)。其实只需要知道末尾有\(18\)个\(0\)就行了,因为在\(x\)......
  • CF1906C Cursed Game 题解
    题目大意交互库有一个\(3\times3\)的01矩阵\(a\),每次询问一个\(n\timesn\)的01矩阵\(b\),交互库会返回一个\((n-2)\times(n-2)\)的01矩阵\(c\),满足:\[c_{x,y}=\bigoplus\limits_{1\lei,j\le3}\left(a_{i,j}\operatorname{AND}b_{x+i-1,y+j-1}\right......
  • 梦熊十三连测第三场题解
    T1本题考察了数论的相关知识。30pts暴力枚举每次洗牌的情况,时间复杂度为\(O(n^2)\)。60pts首先卡牌\(1\)和\(2n\)一直不动,可以不用考虑这两张牌。将位置和剩下的牌上的数字全减\(1\),那么数字为\(k\)的牌操作一次后就会到\(2k\bmod(2n-1)\)的位置。那么问题相当......
  • Maximum Glutton题解
    正常动规,但是赛时死了。分析看到\(n\)很小,但是\(X\)和\(Y\)有点大,所以状态稍微改变一下。设\(dp_{i,j}\)表示已经选到第\(j\)个,且甜度为\(i\)时咸度的最小值。转移方程为:\[dp_{j,k}=\min_{0\lek\lei,a_i\lej\leX}(dp_{j,k},dp_{j-a_i,k-1}+b_i)\]按照\(i,j......
  • CF526G Spiders Evil Plan 题解
    Description给定一棵\(n\)个节点的无根树,每条边有边权。有\(q\)次询问,每次询问给出\(x,y\),你需要选择\(y\)条树上的路径,使这些路径形成一个包含\(x\)的连通块,且连通块中包含的边权和最大。\(n,q\le10^5\),强制在线。Solution考虑只有一组询问怎么快速求答案。容......
  • 【科大讯飞笔试题汇总】2024-07-27-科大讯飞秋招提前批(研发岗)-三语言题解(Cpp/Java/
    ......
  • ABC364 DEF 题解
    ABC364DEF题解D-K-thNearest题目链接赛时想了一个(也许确实是对的)做法,但是代码太难写,一直没写出来……看了官方题解才发现正解其实也很简单……本题最关键的一点是要转换思路:与其考虑“离某个点第\(k\)近的点在哪”,不如考虑“离某个点距离不超过\(x\)的点有多少个”。......
  • 会员购项目面试题解析:高效数据抓取与异常处理
    会员购项目亮点日志记录信息协程异步抓取数据,大大提高抓取速度捕获异常,并添加重试机制源码importloggingimporttimeimportrequestsimportasyncioimportaiohttpfromaiohttpimportContentTypeErrorimportcsv#配置日志logging.basicConfig(level=logging......
  • C++题解(17) 狐猬编程: 640.线段覆盖
    题目描述在一条数轴上,有N条线段,第i条线段的左端点是s[i],右端点是e[i]。如果线段有重叠(即使是端点重叠也算是重叠),则输出“impossible”,如果没有重叠则输出“possible”。输入格式输入文件名:640.in多组测试数据。第一行,一个整数G,表示有G组测试数据。1<=G<=10。每组......
  • [题解]ABC364 A~F
    A-GluttonTakahashi给定\(n\)道菜,每道菜要么是甜的(用sweet表示),要么是咸的(用salty表示)。必须按顺序吃,如果连续吃到\(2\)个甜的菜,就会浑身难受吃不下去了。请问是否能吃完这些菜。按题意模拟即可,只要前\(n-1\)个元素中有连续的sweet就输出No。点击查看代码#include<bits/s......