| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
哪里错了啊,555555555555~~~~~~~·#include <stdio.h>
#include <stdlib.h>
#include <math.h>
const double eps = 1e-8;
const int Maxn = 105;
struct TPoint
{
double x, y;
};
struct TSegment
{
TPoint p1, p2;
};
struct angle
{
double l, r;
};
int parallel(TPoint s1, TPoint e1, TPoint s2, TPoint e2)
{
if(fabs((s1.y - e1.y) * (s2.x - e2.x)
- (s2.y - e2.y) * (s1.x - e1.x)) < eps) return 1;
else return 0;
}
double max(double x, double y)
{
//比较两个数的大小,返回大的数
if(x > y) return x;
else return y;
}
double min(double x, double y)
{
//比较两个数的大小,返回小的数
if(x < y) return x;
else return y;
}
double multi(TPoint p1, TPoint p2, TPoint p0)
{
return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
}
int isIntersected(TPoint s1, TPoint e1, TPoint s2, TPoint e2)
{
if(
(max(s1.x, e1.x) >= min(s2.x, e2.x)) &&
(max(s2.x, e2.x) >= min(s1.x, e1.x)) &&
(max(s1.y, e1.y) >= min(s2.y, e2.y)) &&
(max(s2.y, e2.y) >= min(s1.y, e1.y)) &&
(multi(s2, e1, s1) * multi(e1, e2, s1) >= 0) &&
(multi(s1, e2, s2) * multi(e2, e1, s2) >= 0)
) return 1;
return 0;
}
int get_angle(TSegment seg1, TSegment seg2, angle &a)
{
if(isIntersected(seg1.p1, seg1.p2, seg2.p1, seg2.p2)){
a.l = -1.0;
a.r = 1.0;
}
else if(parallel(seg1.p1, seg1.p2, seg2.p1, seg2.p2)){
if(fabs(seg1.p1.x - seg1.p2.x) < eps) {
// k = inf || k = -inf;
a.l = 1.0;
a.r = 1.0;
return 1;
}
else if(fabs(seg1.p1.y - seg2.p2.y) < eps){
a.l = 0.0;
a.r = 0.0;
}
}
else {
double k1, k2, tmpa, tmpb;
if(isIntersected(seg1.p1, seg2.p1, seg1.p2, seg2.p2)){
//seg1.p1, seg2.p1 seg1.p2, seg2.p2
tmpa = seg1.p1.x - seg2.p1.x;
tmpb = seg1.p1.y - seg2.p1.y;
if(fabs(tmpb) < eps) k1 = 0.0;
else if(fabs(tmpa) < eps) k1 = 1.0;
else k1 = cos(atan(-tmpa / tmpb));
tmpa = seg1.p2.x - seg2.p2.x;
tmpb = seg1.p2.y - seg2.p2.y;
if(fabs(tmpb) < eps) k2 = 0.0;
else if(fabs(tmpa) < eps) k2 = 1.0;
else k2 = cos(atan(-tmpa / tmpb));
if(k1 < k2) a.l = k1, a.r = k2;
else a.l = k2, a.r = k1;
}
else {
//seg1.p1, seg2.p2 seg1.p2, seg2.p1
tmpa = seg1.p1.x - seg2.p2.x;
tmpb = seg1.p1.y - seg2.p2.y;
if(fabs(tmpb) < eps) k1 = 0.0;
else if(fabs(tmpa) < eps) k1 = 1.0;
else k1 = cos(atan(-tmpa / tmpb));
tmpa = seg1.p2.x - seg2.p1.x;
tmpb = seg1.p2.y - seg2.p1.y;
if(fabs(tmpb) < eps) k2 = 0.0;
else if(fabs(tmpa) < eps) k2 = 1.0;
else k2 = cos(atan(-tmpa / tmpb));
if(k1 < k2) a.l = k1, a.r = k2;
else a.l = k2, a.r = k1;
}
}
return 0;
}
int main()
{
int test, n, i, j, k, tag;
TSegment seg[Maxn];
angle a, a1, b;
scanf("%d", &test);
while(test--){
scanf("%d", &n);
for(i = 0;i < n;i++){
scanf("%lf%lf%lf%lf", &seg[i].p1.x,
&seg[i].p1.y, &seg[i].p2.x, &seg[i].p2.y);
}
a1.l = -1.0;
a1.r = 1.0;
tag = 0;
for(i = 0;i < n;i++){
for(j = i + 1;j < n;j++){
get_angle(seg[i], seg[j], a);//得到斜率角的范围 44
if(a1.l - a.r > 0 || a.l - a1.r > 0){
tag = 1;
printf("No!\n");
break;
}
else {
b.l = max(a1.l, a.l);
b.r = min(a1.r, a.r);
a1 = b;
}
}
if(tag == 1) break;
}
if(tag == 0) printf("Yes!\n");
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator