273 - Jack Straws

[Hecton]

If you can find a common point in boh lines then you can say they are connected.

For rod 1 and rod 6, we certainly can find "a" common point in

both lines because they have "infinite many" common points~~

If the argument is right, rod 1 can connect to rod 5 via rod 6.

I'm really confused right now @.@.

one more question, the order of the coordinates shoud'nt

affect the output right?


Thanks for your helping!!

[Jan]

I coded it long ago, and of course I misunderstood the problem. You are right. I have to recode it again.

[volz_kz_g]

I calculated every two straws to check if they were intersected.
And I get the array link[j] to show if straw i is connected with straw j.
Then I used floyd algorithm to get all link[j].

I have tried many i/o but I it doesn't work.

Here is my code

Code: Select all

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <fstream>
#include <complex>
#include <algorithm>
#define rep(i,j,k) for (int i=j;i<=k;++i)
#define rrep(i,j,k) for (int i=j;i>=k;--i)
#define x real()
#define y imag()

using namespace std;

const double eps = 1e-12;
typedef complex<double> point;
point p[2][100];
bool connec[100][100];
int n,T,u,v;

void read(point & p)
{
    cin >> p.x >> p.y;
}

int dblcmp(double k)
{
    if (fabs(k) < eps) return 0;
    if (k>0) return 1;
    else return -1;
}

double cross(point & oa,point & ob)
{
    return (oa.x * ob.y - oa.y * ob.x);
}

double cross(point & o,point & a,point & b)
{
    point oa = a - o;
    point ob = b - o;
    return cross(oa,ob);
}

bool intersect(point & a,point & b,point & p)
{
    if (p.x >= min(a.x,b.x) && 
	p.x <= max(a.x,b.x) &&
	p.y >= min(a.y,b.y) && 
	p.y <= max(a.y,b.y)) return true;
    else return false;
}

bool intersect(point & a,point & b,point & c,point & d)
{
    int d1 = dblcmp(cross(c,d,a));
    int d2 = dblcmp(cross(c,d,b));
    int d3 = dblcmp(cross(a,b,c));
    int d4 = dblcmp(cross(a,b,d));

    if (d1 * d2 < 0 && d3 * d4 < 0) return true;
    if (d1 == 0 && intersect(c,d,a)) return true;
    if (d2 == 0 && intersect(c,d,b)) return true;
    if (d3 == 0 && intersect(a,b,c)) return true;
    if (d4 == 0 && intersect(a,b,d)) return true;
    return false;
}

int main()
{
    ios::sync_with_stdio(false);

    cin >> T;
    rep(t,1,T)
	{
	    memset(connec,false,sizeof(connec));
	    cin >> n;
	    rep(i,1,n) read(p[0][i]),read(p[1][i]),connec[i][i] = true;
	    rep(i,1,n) rep(j,i+1,n) 
		if (intersect(p[0][i],p[1][i],p[0][j],p[1][j]))
		    connec[i][j] = connec[j][i] = true;
	    rep(k,1,n) rep(i,1,n) rep(j,1,n)
		if (i!=j && j!=k && connec[i][k] && connec[k][j])
		    connec[i][j] = true;
	    cin >> u >> v;
	    while (u!=0 && v!=0)
		{
		    if (connec[u][v]) cout << "CONNECTED" << endl;
		    else cout << "NOT CONNECTED" << endl;
		    cin >> u >> v;
		}
	    cout << endl;
	}
    return 0;
}

[brianfry713]

The outputs of two consecutive cases will be separated by a blank line.
Don't print an extra blank line at the end of the output.

[volz_kz_g]

The outputs of two consecutive cases will be separated by a blank line.
Don't print an extra blank line at the end of the output.

Thanks for your reply,I get AC now