poj 1375 Intervals 圆的切线

题意：有一光源，被若干个圆摭住了，求地面上阴影
 
题解：利用向量旋转求出切线与圆的两个交点，根据两点成线得出aX+bY+c=0的直线，令Y=0时，求出地面的坐标，再合并有连接的阴影。
 
//代码如下：
 
 
[cpp] 
#include<iostream> 
#include<cstdio> 
#include<algorithm> 
#include<math.h> 
#define eps 1e-8 
 
//using namespace std; 
const int maxn=1000; 
struct point{double x,y;}; 
struct circle {point cen;double r;}cir[maxn]; 
struct Node{double s,e;}node[maxn]; 
 
double f[maxn][2]; 
point st; 
double distance(point p1,point p2) 
{ 
    return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)); 
} 
void getline(point p1,point p2,double &a,double &b,double &c) 
{ 
    a=p2.y-p1.y; 
    b=p1.x-p2.x; 
    c=p2.x*p1.y-p1.x*p2.y; 
} 
 
void cirinser(circle c,point &inser1,point &inser2)//圆与切线交点(保证st在圆外) 
 
{ 
    point dir; 
    double dis=distance(c.cen,st); 
    double temp=sqrt(dis*dis-c.r*c.r); 
    double sina=temp/dis; 
    double cosa=c.r/dis; 
    dir.x=(st.x-c.cen.x)/dis*c.r; 
    dir.y=(st.y-c.cen.y)/dis*c.r; 
    inser1.x=c.cen.x+(dir.x*cosa-dir.y*sina); 
    inser1.y=c.cen.y+(dir.x*sina+dir.y*cosa); 
     
    inser2.x=c.cen.x+(dir.x*cosa+dir.y*sina); 
    inser2.y=c.cen.y+(-dir.x*sina+dir.y*cosa); 
} 
bool zero(double x){return x>0? x<eps:x>-eps;} 
bool cmp( Node a, Node b) 
{ 
    if(zero(a.s-b.s))return a.e-b.e<0; 
    else return a.s-b.s<0; 
} 
int main() 
{ 
    int n; 
    while(scanf("%d",&n),n) 
    { 
        scanf("%lf%lf",&st.x,&st.y); 
        int i; 
        point inser1,inser2; 
        double a,b,c; 
        for(i=0;i<n;i++) 
        { 
            scanf("%lf%lf%lf",&cir[i].cen.x,&cir[i].cen.y,&cir[i].r); 
            cirinser(cir[i],inser1,inser2); 
            getline(st,inser1,a,b,c); 
            node[i].s=-c/a; 
            getline(st,inser2,a,b,c); 
            node[i].e=-c/a; 
            if(node[i].s-node[i].e>0)std::swap(node[i].s,node[i].e); 
        } 
        std::sort(node,node+n,cmp); 
         
        f[0][0]=node[0].s; 
        f[0][1]=node[0].e; 
        int cnt=0; www.zzzyk.com
        for(i=1;i<n;i++) 
        { 
            if(node[i].s-f[cnt][1]<eps &&node[i].e-f[cnt][1]>0)f[cnt][1]=node[i].e; 
            else if(node[i].s-f[cnt][1]>0) 
            { 
                f[++cnt][0]=node[i].s; 
                f[cnt][1]=node[i].e; 
            } 
        } 
        for(i=0;i<=cnt;i++) 
            printf("%.2lf %.2lf\n",f[i][0],f[i][1]); 
        printf("\n"); 
    } 
    return 0; 
} 

作者：ssslpk

补充：软件开发 , C++ ,