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

终于AC了,注意是直线与线段相交,因为这个调了一下午

Posted by dgzxzyf at 2022-08-10 21:51:38 on Problem 3304
#include<iostream>
#include<cstdio>
#include<cmath>
#define x first
#define y second
using namespace std;
const double EPS=1e-8;
int n,t;
pair<double,double> s[210];
double Max(double a,double b)
{
	if(a>b) return a;
	else return b;
}
double Min(double a,double b)
{
	if(a<b) return a;
	else return b;
}
bool judge(int a,int b,int c,int d)
{
	if(((s[b].x-s[a].x)*(s[c].y-s[a].y)-(s[b].y-s[a].y)*(s[c].x-s[a].x))*((s[b].x-s[a].x)*(s[d].y-s[a].y)-(s[b].y-s[a].y)*(s[d].x-s[a].x))>EPS) return 0;
	else return 1;
}
double dis(int a,int b)
{
	return sqrt((s[a].x-s[b].x)*(s[a].x-s[b].x)+(s[a].y-s[b].y)*(s[a].y-s[b].y));
}
bool check(int a,int b)
{
	if(dis(a,b)<EPS) return 0;
	for(int i=1;i<=n;i++)
	{
		if(!judge(a,b,i*2-1,i*2)) return 0;
	}
	return 1;
}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n); 
		for(int i=1;i<=n;i++)
		{
			scanf("%lf%lf%lf%lf",&s[i*2-1].x,&s[i*2-1].y,&s[i*2].x,&s[i*2].y);
		}
		int flag=0;
		for(int i=1;i<2*n;i++)
		{
			for(int j=i+1;j<=2*n;j++)
			{
				if(check(i,j))
				{
					flag=1;
					break;
				}
			}
			if(flag) break;
		}
		if(flag) printf("Yes!\n");
		else printf("No!\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