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 ecjtu_yuweiwei at 2014-07-19 10:30:47 on Problem 2653
#include<iostream>
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define eps 1e-8
const int Max=100001;
const int NUM=1001;
int num[NUM];
using namespace std;
int sign(double x)
{
    return (x>eps)-(x<-eps);
}
typedef struct Node
{
    double x;
    double y;
}point;
double multi(point p0,point p1,point p2)//叉积
{
	return(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
//相交返回true,否则为false,接口为两线段的端点
bool IsIntersected(point s1,point e1,point s2,point e2)
{
	return(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(s1,s2,e1)*multi(s1,e1,e2)>0)&&(multi(s2,s1,e2)*multi(s2,e2,e1)>0);
}
typedef struct Segment
{
    point s;
    point e;
}segment;
segment s[Max];
int main()
{
    int n,m,i,j,p;
    while(cin>>n&&n)
    {
        memset(num,0,sizeof(num));
        m=0;
        for(i=1;i<=n;i++)
        {
            cin>>s[i].s.x>>s[i].s.y>>s[i].e.x>>s[i].e.y;
        }
        for(i=1;i<n;i++)
        {
            p=0;
            for(j=i+1;j<=n;j++)
            {
                if(IsIntersected(s[i].s,s[i].e,s[j].s,s[j].e))
                {
                    p=1;
                    break;
                }
            }
            if(p==0)
                num[m++]=i;
        }
        num[m]=n;
        cout<<"Top sticks: ";
        for(i=0;i<=m;i++)
        {
            if(i==m)
                cout<<num[i]<<"."<<endl;
            else
                cout<<num[i]<<", ";
        }
    }
    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