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

ccw 1A代码

Posted by 3015216017 at 2018-08-25 22:14:01 on Problem 1127
#include <stdio.h>
#include <algorithm>
#include <iostream>

using namespace std;

struct point{
	long long x, y;
}; 
typedef point vector;

struct segment{
	point a, b;
}k[20];

int cross(vector v1, vector v2){
	return (v1.x*v2.y - v2.x*v1.y);
}

int dot(vector v1, vector v2){
	return (v1.x*v2.x + v1.y*v2.y);
}

long long norm(vector v){
	return v.x*v.x + v.y*v.y;
}

int ccw(point p0, point p1, point p2){
		vector p1p0;
		p1p0.x = p1.x - p0.x;
		p1p0.y = p1.y - p0.y;
		vector p2p0;
		p2p0.x = p2.x - p0.x;
		p2p0.y = p2.y - p0.y;
		int crossv = cross(p1p0, p2p0);
		if(crossv > 0)
			return -1;
		else if(crossv < 0)
			return 1;
		else{
			int dotv = dot(p2p0, p1p0);
			if(dotv < 0)
				return 1;
			else{
				long long normv = norm(p2p0) - norm(p1p0);
				//cout << norm(p2p0) << " " << normv << endl;
				if(normv > 0)
					return -1;
				else
					return 0;
			}
		}
}

int intersect(point p1, point p2, point p3, point p4){
	return (ccw(p1, p2, p3) * ccw(p1, p2, p4) <= 0 &&
			ccw(p3, p4, p1) * ccw(p3, p4, p2) <= 0 );
}

bool intersection(segment s1, segment s2){
	return intersect(s1.a, s1.b, s2.a, s2.b);
}
bool g[15][15];
int main(){
	int n;
	while(cin >> n){
		if(n == 0)
			break;
		for(int i = 1; i <= n; i++){
			cin >> k[i].a.x >> k[i].a.y >> k[i].b.x >> k[i].b.y;
		}
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++)
				g[i][j] = false;
			g[i][i] = true;
		}
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++)
				if(intersection(k[i], k[j]))
					g[i][j] = true;
		}
		for(int k = 1; k <= n; k++)
			for(int i = 1; i <= n; i++)
				for(int j = 1; j <= n; j++)
					g[i][j] = g[i][j] || g[i][k] && g[k][j];
		int e, f;
		while(cin >> e >> f){
			if(e == 0 && f == 0)
				break;
			if(g[e][f])
				cout << "CONNECTED\n";
			else
				cout << "NOT CONNECTED\n";
		}

	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator