首页 > 代码库 > hdu 1700 Points on Cycle 水几何

hdu 1700 Points on Cycle 水几何

已知圆心(0,0)圆周上的一点,求圆周上另外两点使得三点构成等边三角形。

懒得推公式,直接用模板2圆(r1=dist,r2=sqrt(3)*dist)相交水过

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<iterator>
using namespace std;
#define eps 1e-6
typedef long long ll;
inline double sqr(double x)
{
    return x*x;
}
int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}
int sig(double x)
{
    if(fabs(x)<eps) return 0;
    if(x>0) return 1;
    return -1;
}
struct point
{
    double x,y;
    point(){};
    point(double a,double b):x(a),y(b){}
    void input()
    {
        scanf("%lf%lf",&x,&y);
    }
    friend point operator + (const point &a,const point &b)
    {
        return point(a.x+b.x,a.y+b.y);
    }
    friend point operator - (const point &a,const point &b)
    {
        return point(a.x-b.x,a.y-b.y);
    }
    friend bool operator == (const point &a,const point &b)
    {
        return sig(a.x-b.x)==0 && sig(a.y-b.y)==0;
    }
    friend point operator * (const point &a,const double &b)
    {
        return point(a.x*b,a.y*b);
    }
    friend point operator * (const double &a,const point &b)
    {
        return point(a*b.x,a*b.y);
    }
    friend point operator / (const point &a,const double &b)
    {
        return point(a.x/b,a.y/b);
    }
    double norm()
    {
        return sqrt(sqr(x)+sqr(y));
    }
}a,b;
double det(const point &a,const point &b)
{
    return a.x*b.y-a.y*b.x;
}

double dot(const point &a,const point &b)
{
    return a.x*b.x+a.y*b.y;
}
double dist(const point &a,const point &b)
{
    return (a-b).norm();
}
point rotate_point(const point &p,double A)
{
    double tx=p.x,ty=p.y;
    return point(tx*cos(A)-ty*sin(A),tx*sin(A)+ty*cos(A));
}

point rotate(const point &p,double cost,double sint)
{
    double x=p.x,y=p.y;
    return point(x*cost-y*sint,x*sint+y*cost);
}
pair<point,point> crosspoint(point ap,double ar,point bp,double br)
{
    double d=(ap-bp).norm();
    double cost=(ar*ar+d*d-br*br)/(2*ar*d);
    double sint=sqrt(1.0-cost*cost);
    point v=(bp-ap)/(bp-ap).norm()*ar;
    return make_pair(ap+rotate(v,cost,-sint),ap+rotate(v,cost,sint));
}
int main()
{
    int cas;b.x=0;b.y=0;
    scanf("%d",&cas);
    while(cas--)
    {
        a.input();
        double r=dist(a,b);
        pair<point,point> ans=crosspoint(b,r,a,sqrt(3.0)*r);
        double x1=ans.first.x,y1=ans.first.y,x2=ans.second.x,y2=ans.second.y;
        if(y1<y2||y1==y2&&x1<x2) printf("%.3lf %.3lf %.3lf %.3lf\n",x1,y1,x2,y2);
        else printf("%.3lf %.3lf %.3lf %.3lf\n",x2,y2,x1,y1);
    }
    return 0;
}