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

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

who knows test18 please tell me
Послано Stevexx 27 июн 2017 12:43
#include<cstdio>
#include<cstring>
#include<iostream>
#define pii pair<int,int>
#define pdd pair<double,double>
#define mp make_pair
#define F first
#define S second
#define N 210
using namespace std;
int n,m;
int fat[N];
pii e[N];
pdd p[N];
int father(int x) {if(fat[x]!=x) fat[x]=father(fat[x]); return fat[x];}
double calc(pii a,pii b,pii c)  {return (a.F-c.F)*(b.S-c.S)-(b.F-c.F)*(a.S-c.S);}
bool judge(pii a, pii b, pii c, pii d)
{
    if (max(a.F,b.F)<min(c.F,d.F)||max(a.S,b.S)<min(c.S,d.S)||max(c.F,d.F)<min(a.F,b.F)||max(c.S,d.S)<min(a.S,b.S))  return false;
    if (calc(c,b,a)*calc(b,d,a)<0||calc(a,d,c)*calc(d,b,c)<0)  return false;
    return true;
}
int main()
{
    int i,j,x,y;
    scanf("%d %d",&n,&m);
    for(i=1;i<=n;i++) fat[i]=i;
    for(i=1;i<=n;i++) {scanf("%lf %lf",&x,&y); p[i]=mp(x,y);}
    for(i=1;i<=m;i++) {scanf("%d %d",&x,&y); e[i]=mp(x,y); fat[father(x)]=father(y);}
    for(i=m+1;i<=m+n;i++) e[i]=mp(i-m,i-m);
    m+=n;
    for(i=1;i<=m;i++)
        for(j=i+1;j<=m;j++)
            if(judge(p[e[i].F],p[e[i].S],p[e[j].F],p[e[j].S]))
                fat[father(e[i].F)]=father(e[j].F);
    int stan=father(1);
    for(i=1;i<=n;i++) if(father(i)!=stan)
    puts("YES");
    return 0;
}