代碼有點猥瑣。紀(jì)念下第一道幾何
Source Code
Problem: 1556 User: hehexiaobai
Memory: 1092K Time: 0MS
Language: G++ Result: Accepted
Source Code
#include<iostream> // poj 1556
#include<cmath>
#include<cstring>
using namespace std;
const int MAX = 205;
const double epsilon = 1e-10;
const double PI = acos(-1.0);
double min(double a, double b){ return a > b ? b : a; }
double max(double a, double b){ return a > b ? a : b; }
struct Point
{
double x, y;
Point(){}
Point(double a, double b): x(a), y(b){}
Point operator + (Point b){
return Point(x + b.x, y + b.y);
}
Point operator - (Point b){
return Point(x - b.x, y - b.y);
}
double operator * (Point b){
return x* b.y - y *b.x;
}
bool operator == (Point b){
return (fabs(x - b.x)< epsilon) && (fabs(y - b.y) < epsilon);
}
};
Point point[MAX];
double dis[MAX];
bool mp[MAX][MAX];
int nwalls, cntpoint;
int direction(Point &p0, Point & p1, Point & p2)//判斷 p0p2是從向量p1p0繞p0的旋轉(zhuǎn)方向
{
double d = (p2 - p0) * (p1 - p0);
if(fabs(d) < epsilon) return 0; //共線
if(d > 0.0) return 1; //順時針
return -1; //逆時針
}
bool inBox(Point &pi, Point & pj, Point &pk)
{
return min(pi.x , pj.x) <= pk.x && pk.x <= max(pi.x, pj.x) &&
min(pi.y , pj.y) <= pk.y && pk.y <= max(pi.y, pj.y);
}
bool segmentsIntersect(Point &p1, Point & p2, Point & p3, Point & p4)
{
int d1 = direction(p3, p4, p1),
d2 = direction(p3, p4, p2),
d3 = direction(p1, p2, p3),
d4 = direction(p1, p2, p4);
if(d1 * d2 < 0 && d3 * d4 <0)
return true;
if( d1 == 0 && inBox(p3, p4, p1))
return true;
if( d2 == 0 && inBox(p3, p4, p2))
return true;
if( d3 == 0 && inBox(p1, p2, p3))
return true;
if( d4 ==0 && inBox(p1, p2, p4))
return true;
return false;
}
void Dijstra()
{
int i,j ;
double d[MAX][MAX] ;
memset(d, 0, sizeof d);
for( i = 0; i < cntpoint; i ++)
for(j = i + 1; j < cntpoint; j++)
{
d[i][j] = d[j][i] = sqrt((point[i].x - point[j].x) * (point[i].x - point[j].x)
+ (point[i].y - point[j].y)*(point[i].y - point[j].y));
}
const double INF = 1e40;
bool visit[MAX] = {0};
for( i = 0; i < cntpoint; i ++)
dis[i] = INF;
dis[0] = 0.0;
for( i = 0; i <cntpoint; i ++)
{
int index = -1;
double min = INF;
for(j = 0; j < cntpoint; j ++)
if(!visit[j] && fabs(dis[j] - min) > epsilon && dis[j] < min)
{
index = j;
min = dis[j];
}
if(index == -1)return;
visit[index] = true;
for( j = 0; j < cntpoint; j ++)
if(!visit[j] && mp[index][j] == true && dis[j] > dis[index] + d[index][j])
dis[j] = dis[index] + d[index][j];
}
}
int main()
{
int i , j;
while(cin >> nwalls)
{
if( nwalls == -1)break;
memset(point, 0, sizeof point);
memset(mp, 0, sizeof (mp));
memset(dis, 0, sizeof dis);
point[0].x = 0.0;
point[0].y = 5.0;
double x, y1, y2, y3, y4;
cntpoint = 1;
for(i = 1;i <= nwalls; i ++)
{
cin >> x >> y1 >> y2 >> y3 >> y4;
point[cntpoint].x = x;
point[cntpoint].y = 0.0;
cntpoint ++;
point[cntpoint].x = x;
point[cntpoint].y = y1;
cntpoint ++;
point[cntpoint].x = x;
point[cntpoint].y = y2;
cntpoint ++;
point[cntpoint].x = x;
point[cntpoint].y = y3;
cntpoint ++;
point[cntpoint].x = x;
point[cntpoint].y = y4;
cntpoint ++;
point[cntpoint].x = x;
point[cntpoint].y = 10.0;
cntpoint ++;
}
point[cntpoint].x = 10.0;
point[cntpoint].y = 5.0;
cntpoint ++;
int tempi, tempj;
for( i = 0; i < cntpoint ; i ++)
for(j = i + 1; j < cntpoint; j ++)
{
tempi = i / 6;
if( i % 6 != 0) tempi += 1;
tempj = j/6;
if( j % 6 != 0) tempj += 1;
if(tempi == tempj)continue;
if(point[i].y < epsilon || point[j].y < epsilon ||
10.0 - point[i].y < epsilon || 10.0 - point[j].y < epsilon)
continue;
bool flag = true;
for( int k = tempi + 1; k < tempj; k ++)
{
int t = (k - 1) * 6;
// if(i == 0 && j == 9){ cout << flag << endl; cout << t << endl; }
if(segmentsIntersect(point[i],point[j],point[t + 1],point[t + 2]))flag = false;
if(segmentsIntersect(point[i],point[j],point[t + 3],point[t + 4]))flag = false;
if(segmentsIntersect(point[i],point[j],point[t + 5],point[t + 6]))flag = false;
}
if(flag == true)
{
mp[i][j] = mp[j][i] = true;
}
}
// for( i = 0; i < cntpoint; i ++,cout << endl)
// for(j = 0; j < cntpoint; j ++)
// cout << mp[i][j] <<" ";
Dijstra();
// for(i = 0; i < cntpoint ; i ++)
// cout << i <<' '<<dis[i] << endl;
cout.precision(2);
cout <<fixed << dis[cntpoint - 1] << endl;
}
return 0;
}
//0.0 0.0 1.0 1.0 1.0 0.0 1.0 1.0
//0.0 0.0 1.0 1.0 0.0 1.0 1.0 0.0
//0.0 0.0 1.0 1.0 1.0 0.0 1.0 0.9