首页 > 代码库 > ural 2032 Conspiracy Theory and Rebranding （数学水题）
ural 2032 Conspiracy Theory and Rebranding （数学水题）
ural 2032 Conspiracy Theory and Rebranding
链接：http://acm.timus.ru/problem.aspx?space=1&num=2032
题意：给定一个三角形的三条边 (a, b, c)，问是否可放在二维坐标，使得3个顶点都是整数点。若可以，输出任意一组解，否则，输出 -1。
思路：暴力枚举：以 a 为半径做第一象限的 1/4 圆， 以 b 为半径做 一、四 象限的半圆，存储整数点的解，暴力枚举 a 整数点与 b 整数点是否构成长度为 c 的边。
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cmath> 5 #include <cstring> 6 7 using namespace std; 8 typedef long long ll; 9 const int N = 1e5+7;10 ll biao[N];11 ll a, b, c;12 int n;13 14 ll rr, RR;15 16 struct P{17 ll x, y;18 P(ll _x=0, ll _y=0) : x(_x), y(_y) {}19 void out() {printf("%I64d %I64d\n", x, y); }20 }p[N], v[N];21 int ta, tb;22 23 inline ll sqr(ll x) {return x*x;}24 25 inline void init(ll av, ll r, int &t, P q[]) {26 ll aa = av*av;27 for(ll i = 0, j = av; i <= av; ++i) {28 while(sqr(i) + sqr(j) > aa) --j;29 if(sqr(i) + sqr(j) == aa) q[t++] = P(i, j);30 }31 }32 33 inline ll dis(P d1, P d2) {34 return sqr(d1.x - d2.x) + sqr(d1.y - d2.y);35 }36 37 void solve() {38 ta = tb = 0;39 ll cc = c*c;40 init(a, rr, ta, p);41 init(b, RR, tb, v);42 bool f = 0, ff;43 int i, j;44 P q;45 for(i = 0; i < ta; ++i) {46 for(j = 0; j < tb; ++j) {47 ll d = dis(p[i], v[j]);48 if(d == cc) {49 f = 1, ff = 0;50 break;51 } else{52 q = P(v[j].x, -v[j].y);53 d = dis(p[i], q);54 if(d == cc) {55 f = ff = 1;56 break;57 }58 }59 }60 if(f) break;61 }62 if(!f) { puts("-1"); return ; }63 puts("0 0"); p[i].out();64 if(!ff) v[j].out();65 else q.out();66 return ;67 }68 69 int main()70 {71 #ifdef PIT72 freopen("i.in", "r", stdin);73 #endif // PIT74 75 while(~scanf("%I64d %I64d %I64d", &a, &b, &c)) {76 rr = a*a, RR = b*b;77 solve();78 }79 return 0;80 }
ural 2032 Conspiracy Theory and Rebranding （数学水题）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。