学步园

暂存【不好意思，TLE了】

#include <iostream>  
#include <stdlib.h>  
#include <stdio.h>  
#include <math.h>  
#include <algorithm>  
  
using namespace std;  
  
const int maxn = 15;  
const double pi = acos(-1.0);
const double eps = 1e-8;  

int sig(double x)
{
    return (x > eps) - (x < -eps);
}

template <class T>
void read(T *x)
{
	(*x) = 0;
	char ch = getchar();
	bool flag = false;
	while(ch < '0' || ch > '9')
	{
		if(ch == '-')
			flag = true;
		ch = getchar();
		if(ch == EOF)
			return ;
	}
	while(ch >= '0' && ch <= '9')
	{
		(*x) *= 10;
		(*x) += ch - '0';
		ch = getchar();
	}
	if(flag)
		(*x) *= -1;
}
  
typedef struct Point  
{  
    double x, y;  
    Point(double _x = 0.0, double _y = 0.0):  
        x(_x), y(_y) {}  
    Point operator +(const Point argu) const
    {  
        return Point(x + argu.x, y + argu.y);  
    }  
    Point operator -(const Point argu) const 
    {  
        return Point(x - argu.x, y - argu.y);  
    }  
    bool operator <(const Point argu) const 
    {  
        if(sig(x - argu.x) == 0)
            return y < argu.y;
        else
            return x < argu.x;
    }  
    double operator ^(const Point argu) const 
    {  
        return x * argu.y - y * argu.x;  
    }  
    Point operator *(const double k) const
    {  
        return Point(x * k, y * k);  
    }  
    Point operator /(const double k) const 
    {  
        return Point(x / k, y / k);  
    }  
    Point rotate(const double r, const double p) const 
    {  
        return Point(x + r * cos(p), y + r * sin(p));  
    }  
    double dis(const Point argu) const
    {
        return sqrt((x - argu.x) * (x - argu.x) + (y - argu.y) * (y - argu.y));
    }
    void push(const double nx, const double ny)  
    {  
        x = nx;  
        y = ny;  
    }  
    void in(void)  
    {  
        read(&x);
        read(&y);
    }  
    void out(void) const  
    {  
        printf("%.3lf %.3lf\n", x, y);  
    }  
}Vector;

Point Get_Intersection(Point u1, Point u2, Point v1, Point v2)
{
	Point ret = u1;
	double t = ((u1.x - v1.x) * (v1.y - v2.y) - (u1.y-v1.y) * (v1.x - v2.x))
			/ ((u1.x - u2.x) * (v1.y - v2.y) - (u1.y - u2.y) * (v1.x - v2.x));
	ret.x += (u2.x - u1.x) * t;
	ret.y += (u2.y - u1.y) * t;
	return ret;
}  

void Intersection_Line_Circle(Point c, double r, Point l1, Point l2, Point& p1, Point& p2)
{
	Point p = c;
	double t;
	p.x += l1.y - l2.y;
	p.y += l2.x - l1.x;
	p = Get_Intersection(p, c, l1, l2);
	t = sqrt(r * r - (p.x - c.x) * (p.x - c.x) - (p.y - c.y) * (p.y - c.y)) / l1.dis(l2);
	p1.x = p.x + (l2.x - l1.x) * t;
	p1.y = p.y + (l2.y - l1.y) * t;
	p2.x = p.x - (l2.x - l1.x) * t;
	p2.y = p.y - (l2.y - l1.y) * t;
}

double Dis_Line(Point a, Point b, Point p)
{
    return fabs((a - p) ^ (b - p)) / 2.0 / a.dis(b);
}

Point O, p1, p2, m1, m2, m3, m4;
double r, s, d, h, ang;
int x[4], y[4];

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}
int num(int x1, int y1, int x2, int y2)
{
    int a = y2 - y1;
    int b = x2 - x1;
    if(a < 0)
		a *= -1;
    int k = gcd(a, b);
    return k + 1;
}

int solve(Point ma, Point mb, double f)
{
    Point ja, jb;
    Intersection_Line_Circle(O, r, ma, mb, ja, jb);
    //ja.out();
    //jb.out();
    if(jb < ja)
    {
        Point tmp = ja;
        ja = jb;
        jb = tmp;
    }
    int xa, ya, xb, yb;
    xa = ceil(ja.x); 
    xb = floor(jb.x);
    if(xb < xa)
        return 0;
    if(sig(ja.x - jb.x) == 0)
    {
        ya = ceil(ja.y);
        yb = floor(jb.y);
        if(yb < ya)
            return 0;
        else
            return yb - ya + 1;
    }
    if(sig(ja.y - jb.y) == 0)
            return xb - xa + 1;
    double k = (ja.y - jb.y) / (ja.x - jb.x);
    double tmpk;
    //此处两个while循环会TLE
    while(xa <= xb)
    {
        ya = ja.y - k * (ja.x - xa);
        tmpk = (ja.y - ya) / (ja.x - xa);
        if(sig(k - tmpk) == 0)
            break;
        xa++;
    }
    while(xa <= xb)
    {
        yb = ja.y - k * (ja.x - xb);
        tmpk = (ja.y - yb) / (ja.x - xb);
        if(sig(k - tmpk) == 0)
            break;
        xb--;
    }
    tmpk = ((double)ya - (double)yb) / ((double)xa - (double)xb);
    if(xa == xb && ya == yb && sig(k - tmpk) == 0)
        return 1;
    return num(xa, ya, xb, yb);
}

int work()
{
    int ans = 0;
    O.in();
    //scanf("%lf", &r);
    read(&r);
    p1.in();
    p2.in();
    d = p1.dis(p2);
    h = s / d;
    ang = fmod(atan2(p2.y - p1.y, p2.x - p1.x) + 2 * pi, 2 * pi);
    
    m1 = p1.rotate(h, ang + 0.5 * pi); 
    m2 = p2.rotate(h, ang + 0.5 * pi);
    m3 = p1.rotate(h, ang - 0.5 * pi); 
    m4 = p2.rotate(h, ang - 0.5 * pi);
    //m1.out();
    //m2.out();
    //m3.out();
    //m4.out();
    
    if(sig(Dis_Line(m1, m2, O) - r) <= 0)
        ans += solve(m1, m2, 1.0);
    if(sig(Dis_Line(m3, m4, O) - r) <= 0)
        ans += solve(m3, m4, -1.0);
    return ans;
}
  
int main()  
{
    //freopen("G.in", "r", stdin);
    
    int cas;
    //scanf("%d", &cas);
    read(&cas);
    while(cas--)
    {
        //scanf("%lf", &s);
        read(&s);
        printf("%d\n", work());
    }
    return 0;  
}