首页 > 代码库 > 【BZOJ】1074: [SCOI2007]折纸origami
【BZOJ】1074: [SCOI2007]折纸origami
http://www.lydsy.com/JudgeOnline/problem.php?id=1074
题意:一开始有一个左上角是(0,100),右下角是(100,0)的纸片,现在可以沿有向直线折n次(n<=8,右边折向左边),折完后,有m个询问(m<=50),每次询问一个点在最终的图形中穿过了几次纸片。
#include <cstdio>#include <cstring>#include <cmath>#include <string>#include <iostream>#include <algorithm>#include <queue>#include <set>#include <map>#include <sstream>using namespace std;typedef long long ll;#define pb push_back#define rep(i, n) for(int i=0; i<(n); ++i)#define for1(i,a,n) for(int i=(a);i<=(n);++i)#define for2(i,a,n) for(int i=(a);i<(n);++i)#define for3(i,a,n) for(int i=(a);i>=(n);--i)#define for4(i,a,n) for(int i=(a);i>(n);--i)#define CC(i,a) memset(i,a,sizeof(i))#define read(a) a=getint()#define print(a) printf("%d", a)#define dbg(x) cout << (#x) << " = " << (x) << endl#define error(x) (!(x)?puts("error"):0)#define rdm(x, i) for(int i=ihead[x]; i; i=e[i].next)inline int getint() { static int r, k; r=0,k=1; static char c; c=getchar(); for(; c<‘0‘||c>‘9‘; c=getchar()) if(c==‘-‘) k=-1; for(; c>=‘0‘&&c<=‘9‘; c=getchar()) r=r*10+c-‘0‘; return k*r; }const double eps=1e-6, PI2=acos(-1)*2;int dcmp(double x) { return abs(x)<eps?0:(x<0?-1:1); }struct iP { double x, y; iP(double _x=0, double _y=0):x(_x),y(_y){} void rd() { scanf("%lf%lf", &x, &y); } void D() { printf("x=%.2f, y=%.2f\n", x, y); }};typedef iP iV;iV operator-(iP a, iP b) { return iV(a.x-b.x, a.y-b.y); }iV operator*(iV a, double b) { return iV(a.x*b, a.y*b); }iV operator+(iP a, iV b) { return iP(a.x+b.x, a.y+b.y); }bool operator==(iP a, iP b) { return dcmp(a.x-b.x)==0 && dcmp(a.y-b.y)==0; }bool operator<(const iP &a, const iP &b) { return a.x==b.x?a.y<b.y:a.x<b.x; }double cross(iV a, iV b) { return a.x*b.y-a.y*b.x; }double dot(iV a, iV b) { return a.x*b.x+a.y*b.y; }double Length(iV a) { return sqrt(dot(a, a)); }double angle(iV a, iV b) { return acos(dot(a, b)/Length(a)/Length(b)); }iV rot(iV v, double ang) { double cs=cos(ang), sn=sin(ang); return iV(v.x*cs-v.y*sn, v.y*cs+v.x*sn); }struct iL { iP p; iV v; iL(){} iL(iP _p, iV _v):p(_p),v(_v) {} };bool onL(iP a, iL l) { return dcmp(cross(a-l.p, l.v))<0; }bool onR(iP a, iL l) { return dcmp(cross(a-l.p, l.v))>0; }iP rev(iP a, iL l, int flag=1) { return l.p+rot(a-l.p, angle(a-l.p, l.v)*2*flag); }const int Mx=1<<10;iP h[Mx];iL line[10];int n, m, cnt;void dfs(int dep, iP p) { //if(dcmp(p.x)<=0 || dcmp(p.x-100)>=0 || dcmp(p.y)<=0 || dcmp(p.y-100)>=0) return; h[cnt++]=p; if(dep==0) return; dfs(dep-1, p); if(onL(p, line[dep])) dfs(dep-1, rev(p, line[dep], -1));}iP find(iP p) { for1(i, 1, n) if(onR(p, line[i])) p=rev(p, line[i]); else if(!onL(p, line[i])) return iP(-1, -1); return p;}bool check(iP &p) { if(dcmp(p.x)<=0 || dcmp(p.x-100)>=0 || dcmp(p.y)<=0 || dcmp(p.y-100)>=0) return false; return true; }void work(iP &p) { //if(dcmp(p.x)<=0 || dcmp(p.x-100)>=0 || dcmp(p.y)<=0 || dcmp(p.y-100)>=0) { puts("0"); return; } int ans=0; cnt=0; dfs(n, p); sort(h, h+cnt); cnt=unique(h, h+cnt)-h; rep(i, cnt) if(check(h[i]) && find(h[i])==p) ++ans; printf("%d\n", ans);}int main() { read(n); for1(i, 1, n) { iP p1, p2; p1.rd(); p2.rd(); line[i]=iL(p1, p2-p1); } read(m); for1(i, 1, m) { iP p; p.rd(); work(p); } return 0;}
这题很神....
看了题解简直惊呆了QAQ逆向思维...
首先我们对于每个点,我们先看看这个点可能由哪些点转移而来(按折纸顺序排序的折纸操作的子集),最多只有$2^8$个这样的点。最后我们再枚举这些点看能否折回原来的点。(注意,如果折的时候正在判定的点在这个直线上,那么这是无解的,因为穿过边界不算。而且永远也不会有正方形的一部分覆盖到这里了)
但是我陷入到了计算几何调试不出来的坑...想个问题似乎想了2h.................................................sb错1:计算向量之间的角我竟让忘记打上acos......调了无数次.... sb错2:输出调试了老半天,浪费大量时间...(难道就不能好好想想吗...
果然状态太差不适合做题
【BZOJ】1074: [SCOI2007]折纸origami
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。