# ZOJ 1648 Circuit Board（计算几何）

Circuit Board Time Limit: 2 Seconds Memory Limit: 65536 KB On the circuit board, there are lots of circuit paths. We know the basic constrain is that no two path cross each other, for otherwise the board will be burned.

Now given a circuit diagram, your task is to lookup if there are some crossed paths. If not find, print “ok!”, otherwise “burned!” in one line.

A circuit path is defined as a line segment on a plane with two endpoints p1(x1,y1) and p2(x2,y2).

You may assume that no two paths will cross each other at any of their endpoints.

Input

The input consists of several test cases. For each case, the first line contains an integer n(<=2000), the number of paths, then followed by n lines each with four float numbers x1, y1, x2, y2.

Output

If there are two paths crossing each other, output “burned!” in one line; otherwise output “ok!” in one line.

Sample Input

1 0 0 1 1

2 0 0 1 1 0 1 1 0

Sample Output

ok! burned!

```#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
struct Point
{
double x,y;
}a[2005][2];
int n;
double mult(Point a, Point b, Point c)
{
return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y);
}

//aa, bb为一条线段两端点 cc, dd为另一条线段的两端点 相交返回true, 不相交返回false
bool intersect(Point aa, Point bb, Point cc, Point dd)
{
if ( max(aa.x, bb.x)<min(cc.x, dd.x) )
{
return false;
}
if ( max(aa.y, bb.y)<min(cc.y, dd.y) )
{
return false;
}
if ( max(cc.x, dd.x)<min(aa.x, bb.x) )
{
return false;
}
if ( max(cc.y, dd.y)<min(aa.y, bb.y) )
{
return false;
}
if ( mult(cc, bb, aa)*mult(bb, dd, aa)<0 )
{
return false;
}
if ( mult(aa, dd, cc)*mult(dd, bb, cc)<0 )
{
return false;
}
return true;
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
for(int i=1;i<=n;i++)
scanf("%lf%lf%lf%lf",&a[i][0].x,&a[i][0].y,&a[i][1].x,&a[i][1].y);
bool tag=true;
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
if(intersect(a[i][0],a[i][1],a[j][0],a[j][1]))
{tag=false;break;}
}
if(!tag)
break;
}
if(!tag)
printf("burned!\n");
else
printf("ok!\n");
}
return 0;
}```

435 篇文章42 人订阅

0 条评论

## 相关文章

### POJ 3278 Catch That Cow(BFS,板子题)

Catch That Cow Time Limit: 2000MS Memory Limit: 65536K Total Submissions...

2955

842

### Codefoces 723B Text Document Analysis

B. Text Document Analysis time limit per test:1 second memory limit per test:256...

35510

1663

### LWC 63: 750. Number Of Corner Rectangles

LWC 63: 750. Number Of Corner Rectangles 传送门：750. Number Of Corner Rectangles Pr...

2297

976

2168

894

3023

1136