Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## Re:怎么可能是TLE呢！！！！！怎么可能。。。才10^6！！！

Posted by flyzer at 2019-05-27 17:21:44 on Problem 3304
In Reply To:怎么可能是TLE呢！！！！！怎么可能。。。才10^6！！！ Posted by:severous at 2011-08-15 14:44:25
```> #include<cstdio>
> using namespace std;
> struct point {
>     double x;
>     double y;
>     };
> bool judge(point p1,point p2,point p3)
> {
>  if((p2.x-p1.x)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x)==0)
>  return true;
>  else
>  return false;
> }
> point inter(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;
> }
> main(){
>     int t,cont,flag,n,i,j,k;
>     struct point a[220],ret;
>     double x1,x2,y1,y2;
>     scanf("%d",&t);
>     while(t--){
>         flag=1;
>         scanf("%d",&n);
>         for(i=0;i<=2*n-1;i++){
>             scanf("%lf%lf",&a[i].x,&a[i].y);
>             }
>             for(i=0;i<=2*n-1 && flag;i++){
>                 for(j=i+1;j<=2*n-1 && flag;j++){
>                     cont=0;
>                     for(k=0;k<=2*n-1 && flag;k=k+2){
>                       if(judge(a[i],a[j],a[k])&&judge(a[i],a[j],a[k+1]))
>                         cont++;
>                         else{
>                             ret=inter(a[i],a[j],a[k],a[k+1]);
>                             if(a[k].x>a[k+1].x){
>                                 x1=a[k+1].x;
>                                 x2=a[k].x;
>                                 }
>                                 else{
>                                     x1=a[k].x;
>                                     x2=a[k+1].x;
>                                     }
>                                if(a[k].y>a[k+1].y){
>                                 y1=a[k+1].y;
>                                 y2=a[k].y;
>                                 }
>                                 else{
>                                     y1=a[k].y;
>                                     y2=a[k+1].y;
>                                     }
>                                     if(ret.x<=x2 && ret.x>=x1 && ret.y<=y2 && ret.y>=y1)
>                                     cont++;
>                             }
>                         }
>                         if(cont==n)
>                          flag=0;
>                     }
>                 }
>                 if(flag==0)
>                 printf("Yes!\n");
>                 else
>                 printf("No!\n");
>         }
>
>
>     }
```

Followed by: