ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1966. Велодорожки

WA on test 9
Послано zhaimingshuzms 28 июн 2017 16:40
What's wrong?
#include<cstdio>
using namespace std;
const int N=201;
struct Node{int x,y;}a[N];
struct Line{int s,t;}b[N];
int fa[N],n,m,root;
inline int direct(Node x,Node y,Node z){
    return (y.x-x.x)*(z.y-x.y)-(y.y-x.y)*(z.x-x.x);
}
bool online(Node x,Line y){//right
    Node be=a[y.s],en=a[y.t];
    if (x.x<be.x||x.x>en.x) return 0;
    if (direct(be,x,en)==0) return 1;
    return 0;
}
bool cross(Line x,Line y){
    Node p1=a[x.s],p2=a[x.t],p3=a[y.s],p4=a[y.t];
    if (online(p1,y)||online(p2,y)||online(p3,x)||online(p4,x)) return 1;
    int d1=direct(p1,p2,p3),d2=direct(p1,p2,p4),d3=direct(p3,p4,p1),d4=direct(p3,p4,p2);
    if ((d1^d2)<0&&(d3^d4)<0) return 1;
    return 0;
}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void unite(int x,int y){
    x=find(x); y=find(y);
    if (x<y) fa[y]=x; else if (x>y) fa[x]=y;
}
int main(){
    scanf("%d%d",&n,&m);
    for (int i=1; i<=n; i++) fa[i]=i;
    for (int i=1; i<=n; i++) scanf("%d%d",&a[i].x,&a[i].y);
    for (int i=1; i<=m; i++){
        scanf("%d%d",&b[i].s,&b[i].t); unite(b[i].s,b[i].t);
        for (int j=1; j<=n; j++)if (online(a[j],b[i])) unite(j,b[i].s);
        for (int j=1; j<i; j++) if (cross(b[i],b[j])) unite(b[i].s,b[j].s);
    }
    root=find(1);
    for (int i=2; i<=n; i++) if (find(i)!=root) {printf("NO"); return 0;}
    printf("YES");
    return 0;
}