Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define readFile freopen("in.txt","r",stdin)
- #define writeFile freopen("out.txt","w",stdout)
- #define fastio ios_base::sync_with_stdio(false)
- using namespace std;
- const int N = 100010;
- const long long M = 1e9 + 7;
- #define eps 1e-9
- #define PI acos(-1.0)
- double sqr(double x){
- return x*x;
- }
- struct point{
- double x,y;
- point():x(0),y(0){}
- point(double x, double y):x(x),y(y){}
- double dist(const point &p){
- return hypot(this->x-p.x,this->y-p.y);
- }
- };
- struct circle{
- point p;
- double r;
- circle():p(),r(0){}
- circle(point p, double r):p(p.x,p.y),r(r){}
- };
- struct line{
- // ax + by + c = 0;
- double a,b,c;
- line(){}
- line(double a, double b, double c):a(a),b(b),c(c){}
- line(point p1, point p2){
- if(abs(p1.x-p2.x) < eps){ // vertical
- a = 1.0;
- b = 0.0;
- c = -p1.x;
- }
- else{
- a = -(p1.y-p2.y)/(p1.x-p2.x);
- b = 1.0;
- c = -(a*p1.x)-p1.y;
- }
- }
- };
- struct triangle{
- double a,b,c;
- triangle(){}
- triangle(point p1, point p2, point p3){
- a = p1.dist(p2);
- b = p2.dist(p3);
- c = p1.dist(p3);
- }
- double area(){
- double sp = (a+b+c)/2.0;
- double res = sp*(sp-a)*(sp-b)*(sp-c);
- return sqrt(res);
- }
- double findTheta(){
- double aa = a, bb = b, cc = c;
- if(bb > aa) swap(aa,bb);
- if(cc > aa) swap(aa,cc);
- double costheta = (sqr(bb)+sqr(cc)-sqr(aa))/(2.0*bb*cc);
- return acos(costheta);
- }
- };
- int lineCircleIntersection(circle cr, line l, point &p1, point &p2){
- if(abs(l.b)<eps){ // Vertical line, the equation is already solved for x .
- double a = 1.0;
- double b = -2.0 * cr.p.y;
- double c = sqr(l.c/l.a-cr.p.x) + sqr(cr.p.y) - sqr(cr.r);
- double d = sqr(b) - 4.0 * a * c;
- if(d+eps < 0) return 0; // No intersection .
- if(abs(d) < eps){
- p1.x = l.c/l.a;
- p1.y = -b/(2.0*a);
- return 1; // Tangent line .
- }
- double dd = sqrt(d);
- p1.x = p2.x = l.c/l.a;
- p1.y = (-b+dd)/(2.0*a);
- p2.y = (-b-dd)/(2.0*a);
- return 2; // Intersect in two points .
- }
- else{
- double a = 1.0 + l.a;
- double b = 2.0 * (l.a*l.c - cr.p.x + cr.p.y*l.a);
- double c = sqr(cr.p.x) + sqr(cr.p.y) + sqr(l.c) - sqr(cr.r) - (2.0*cr.p.y*l.c);
- double d = sqr(b) - 4.0 * a * c;
- if(d+eps < 0) return 0; // No intersection .
- if(abs(d) < eps){
- p1.x = -b/(2.0*a);
- p1.y = -p1.x - l.c;
- return 1; // Tangent line .
- }
- double dd = sqrt(d);
- p1.x = (-b+dd)/(2.0*a);
- p1.y = -(p1.x*l.a) - l.c;
- p2.x = (-b-dd)/(2.0*a);
- p2.y = -(p2.x*l.a) - l.c;
- return 2; // Intersect in two points .
- }
- }
- int main() {
- #ifndef ONLINE_JUDGE
- readFile;
- #endif
- fastio;
- int t,tt = 1; cin >> t;
- while(t--){
- double x,y,z; cin >> x >> y >> z;
- circle c(point(x,y),z);
- double x1,y1,x2,y2; cin >> x1 >> y1 >> x2 >> y2;
- point p1(x1,y1),p3(x2,y2);
- point p2(p1.x,p3.y);
- line l1(p2,p3), l2(p1,p2);
- point pt1,pt2,cl1,cl2;
- int res = lineCircleIntersection(c,l1,pt1,pt2);
- if(res==2){
- if(pt1.x > pt2.x) cl1 = pt1;
- else if(pt2.x > pt1.x) cl1 = pt2;
- else if(pt1.y < pt2.y) cl1 = pt1;
- else cl1 = pt2;
- }
- else cl1 = pt1;
- res = lineCircleIntersection(c,l2,pt1,pt2);
- if(res==2){
- if(pt1.y < pt2.y) cl2 = pt1;
- else if(pt2.y < pt1.y) cl2 = pt2;
- else if(pt1.x > pt2.x) cl2 = pt1;
- else cl2 = pt2;
- }
- else cl2 = pt1;
- triangle t1(cl1,cl2,c.p);
- double cseg = ((t1.findTheta()*sqr(c.r))/2.0)-t1.area();
- triangle t2(cl1,p2,cl2);
- double ans = cseg + t2.area();
- cout << "Case " << tt++ << ": ";
- cout << fixed << setprecision(8) << ans << "\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement