I - Conspiracy Theory and Rebranding
Time Limit:1000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u
Description
Today is a great day! The Secret World Government has entrusted you with the task of rebranding the sign whose roots stretch back to ancient times. According to the trend of interface flattening promoted by technological subsidiaries of the World Government (see Windows 8 and iOS 7), the new logo will be implemented as a triangle drawn on a plane.
Of course, the logo must be highly conspiratorial, that is why it will contain a cryptic message expressed in special values of the lengths of its sides. Since the message is cryptic, you won’t know these values. The logo will be placed on the main page of the World Government’s secret website, which is adapted for viewing on rereretina displays. It is well known that displays of this type use Cartesian coordinate system. If the coordinates of at least one vertex of the triangle are not integers, the lengths of the sides can be distorted and the secret message won’t be delivered to recipients.
To unravel this tangle of secrets, you decided to write a program for finding a location of a triangle with given lengths of sides on a plane such that all the vertices would have integer coordinates. Then the World Government’s high-ranking officials will be able to run your program and get a new logo without you knowing the secret lengths. It’s time to start!
Input
The only input line contains three positive integers not exceeding 10 7; they are the lengths of the sides of the triangle. The integers are separated with a space. It is guaranteed that the lengths of sides satisfy the triangle inequality.
Output
If the required triangle doesn’t exist, output “-1” (without quotation marks). Otherwise, output three pairs of integers with absolute values not exceeding 10 8, which are the coordinates of the vertices of the triangle in arbitrary order. The integers must be separated with a space and/or line breaks. If there are several answers, output any of them.
Sample Input
| input | output |
|---|---|
4 3 5 |
0 0 3 4 3 0 |
10 17 21 |
0 0 0 21 -8 15 |
100 100 100 |
-1 |
题意：给出三个边（一定是三角形），然后求这三个点的整数坐标！
题解：先固定一个点在原点，然后通过一个边求另一个点的整数坐标，用数组全部记录，注意：求出的点都是正整数点；因为开方的原因，所以要列出所有可能的点出来。然后就是一个个枚举另一个整数点。
#include <iostream> #include <cmath> #include <cstring> #include <algorithm> using namespace std; typedef long long LL; LL a[3]; LL b[3]; LL c[100005]; LL d[100005]; bool cp; int dx[] = {1,1,-1,-1}; int dy[] = {1,-1,1,-1}; int get(LL w,LL x,LL y,LL z) { if(((w-y)*(w-y)+(x-z)*(x-z))==(a[0]*a[0])) { //cout<<w<<" "<<x<<" "<<y<<" "<<z<<endl; //cout<<((w-y)*(w-y)+(x-z)*(x-z))<<" "<<(a[0]*a[0])<<endl; return 1; } return 0; } int get1(LL n) { long double f = sqrt((long double)(a[1]*a[1]-n*n)); b[1] = f; if(f==b[1]) return 1; return 0; } int get2(LL n) { long double f = sqrt((long double)(a[2]*a[2]-n*n)); b[2] = f; if(f==b[2]) return 1; return 0; } int main() { ios::sync_with_stdio(0); while(cin>>a[0]>>a[1]>>a[2]) { sort(a,a+3); memset(b,0,sizeof(b)); //cout<<a[0]<<" "<<a[1]<<" "<<a[2]<<endl; cp=false; int num=0; for(LL i=0;i<=a[1];i++) if(get1(i)) { for(int k=0;k<4;k++) { c[num]=i*dx[k]; d[num++]=b[1]*dy[k]; } } //for(int i=0;i<num;i++) cout<<c[i]<<" "<<d[i]<<endl; LL w,x,y,z; for(LL i=0;i<=a[2]&&!cp;i++) if(get2(i)) { for(LL j=0;j<num&&!cp;j++) { for(int k=0;k<4;k++) { w=i*dx[k];x=b[2]*dy[k]; if(get(w,x,c[j],d[j])) { cp=true; y=c[j];z=d[j]; break; } } } } if(!cp) cout<<-1<<endl; else { cout<<0<<" "<<0<<endl; cout<<w<<" "<<x<<endl; cout<<y<<" "<<z<<endl; } } return 0; }