BZOJ1074 [SCOI2007]折纸origami
2024-09-01 07:10:08
我们先看每个点可能从哪些点折过来的，2^10枚举对角线是否用到。
然后再模拟折法，查看每个点是否满足要求。
恩，计算几何比较恶心，还好前几天刚写过一道更恶心的计算几何，点类直接拷过来2333。
/**************************************************************
Problem: 1074
User: rausen
Language: C++
Result: Accepted
Time:24 ms
Memory:980 kb
****************************************************************/ #include <cstdio>
#include <cmath>
#include <algorithm> using namespace std;
typedef double lf; const int N = ;
const lf eps = 1e-; int n, cnt; inline lf sqr(lf x) {
return x * x;
} inline int dcmp(lf x) {
return fabs(x) <= eps ? : (x > eps ? : -);
} struct point {
lf x, y;
point() {}
point(lf _x, lf _y) : x(_x), y(_y) {} inline point operator + (point p) {
return point(x + p.x, y + p.y);
}
inline point operator - (point p) {
return point(x - p.x, y - p.y);
}
inline lf operator * (point p) {
return x * p.y - y * p.x;
}
inline lf operator % (point p) {
return x * p.x + y * p.y;
}
inline point operator * (lf a) {
return point(x * a, y * a);
}
inline point operator / (lf a) {
return point(x / a, y / a);
} inline bool operator < (const point &p) const {
return dcmp(x - p.x) == ? dcmp(y - p.y) < : dcmp(x - p.x) < ;
}
inline bool operator != (const point &p) const {
return dcmp(x - p.x) || dcmp(y - p.y);
}
inline bool operator == (const point &p) const {
return !dcmp(x - p.x) && !dcmp(y - p.y);
} inline void read_in() {
scanf("%lf%lf", &x, &y);
}
friend inline lf dis2(point p) {
return sqr(p.x) + sqr(p.y);
}
friend inline lf dis(point p) {
return sqrt(dis2(p));
}
friend inline lf angle(point p, point q) {
return acos(p % q / dis(p) / dis(q));
}
friend inline point rotate(point p, lf A) {
lf s = sin(A), c = cos(A);
return point(p.x * c - p.y * s, p.x * s + p.y * c);
}
} ans[N << ]; struct line {
point p, v;
line() {}
line(point _p, point _v) : p(_p), v(_v){}
} l[N]; inline point reverse(point p, line l, int f) {
return l.p + rotate(p - l.p, angle(p - l.p, l.v) * * f);
} inline bool on_left(point p, line l) {
return dcmp((p - l.p) * l.v) < ;
} inline bool on_right(point p, line l) {
return dcmp((p - l.p) * l.v) > ;
} void dfs(point p, int d) {
ans[++cnt] = p;
if (d == ) return;
dfs(p, d - );
if (on_left(p, l[d])) dfs(reverse(p, l[d], -), d - );
} inline bool check(lf x) {
return dcmp(x) > && dcmp(x - ) < ;
} inline bool check(point p) {
return check(p.x) && check(p.y);
} inline point find(point p) {
int i;
for (i = ; i <= n; ++i)
if (on_right(p, l[i])) p = reverse(p, l[i], );
else if (!on_left(p, l[i])) return point(-, -);
return p;
} int work(point p) {
int res = , i;
cnt = ;
dfs(p, n);
sort(ans + , ans + cnt + );
cnt = unique(ans + , ans + cnt + ) - ans - ;
for (i = ; i <= cnt; ++i)
if (check(ans[i]) && find(ans[i]) == p) ++res;
return res;
} int main() {
int i, Q;
point x, y;
scanf("%d", &n);
for (i = ; i <= n; ++i) {
x.read_in(), y.read_in();
l[i] = line(x, y - x);
}
scanf("%d", &Q);
while (Q--) {
x.read_in();
printf("%d\n", work(x));
}
return ;
}
最新文章
- 关于.9.png格式图片的制作与使用
- rgb转16进制 简单实现
- Reveal的使用及破解方法
- Mysql分区技术
- HDU 3790 最短路径问题【Dijkstra】
- Simple guide to Java Message Service (JMS) using ActiveMQ
- Redis未授权访问缺陷让服务器沦为肉鸡
- freemarker入门教程
- Linux的正则表达式grep,egrep
- Django中url的生成过程详解
- tcpdump抓包常用命令列举
- 深深感受 Promise.all 带来的速度提升
- MySQL：测试题
- (转)Sphinx中文分词安装配置及API调用
- 强力上攻后，缓解期结束，MACD死叉的案例
- ParseCrontab类，解析时间规则
- [转]Apache 配置虚拟主机三种方式
- 云存储(Swift+Keystone)部署策略
- ZOJ 3992 One-Dimensional Maze（思维题）
- Chapter1（预科）--C++Prime笔记