1147 pick-up sticks.cpp

威士忌的HDU题解.大概有260多题的源码。对于学习非常有好处。

#include <cstdio> 
#include <cmath> 
using namespace std; 
int n,tlen; 
struct Point 
{ 
    double x,y; 
}line[100010][2]; 

inline bool insertLine(Point a,Point c,Point b,Point d) 
{ 
    double t1,t2, num1, num2,num3,num4; 
    num1  = (a.y - c.y)*(d.x - c.x) - (a.x - c.x)*(d.y - c.y);//(d-c)**(a-c) 
    num2  = (a.y - c.y)*(b.x - c.x) - (a.x - c.x)*(b.y - c.y);//(b-c)**(a-c) 
     
    num3  = (d.y - b.y)*(a.x - b.x) - (d.x - b.x)*(a.y - b.y);//(d-b)**(a-b) 
    num4  = (c.x - b.x)*(d.y - b.y) - (c.y - b.y)*(d.x - b.x);//(d-b)**(c-b) 
     
    t1=num1*num2; 
    t2=num3*num4; 
    if( t1<=0 && t2<=0) 
        return true; 
    else 
        return false; 
} 

int main() 
{ 
    int i,j,k; 
    bool flag,dot; 
     
    while(scanf("%d",&n)==1 && n) 
    { 
        tlen=0; 
        for(i=0;i<n;i++) 
        {         
            scanf("%lf %lf %lf %lf",&line[i][0].x,&line[i][0].y,&line[i][1].x,&line[i][1].y); 
        } 
        dot=false; 
        printf("Top sticks:"); 
        for(i=0;i<n;i++) 
        { 
            flag=true; 
            for(j=i+1;j<n;j++) 
                if( insertLine(line[i][0],line[i][1],line[j][0],line[j][1])==true ) 
                { 
                    flag=false; 
                    break; 
                } 
            if(flag) 
            { 
                if(dot) 
                    printf(","); 
                else 
                    dot=true; 
                printf(" %d",i+1); 
            } 
        } 
        printf(".\n"); 
    } 
    return 0; 
}