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

Обсуждение задачи 1103. Карандаши и окружности

I got WA on test #7
Послано Zhang Chihao 3 май 2006 21:53
Can someone help me?

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;

struct Tpoint{
    double x,y;
};

const double eps=1e-8;
const double inf=2147483647.0;

int n;
Tpoint p[6000];
int id[6000];

int dcmp(double x){
    return x<-eps?-1:x>eps;
}

double cross(Tpoint p0,Tpoint p1,Tpoint p2){
    double x1=p1.x-p0.x;
    double x2=p2.x-p0.x;
    double y1=p1.y-p0.y;
    double y2=p2.y-p0.y;
    return x1*y2-x2*y1;
}

double dot(Tpoint p0,Tpoint p1,Tpoint p2){
    double x1=p1.x-p0.x;
    double x2=p2.x-p0.x;
    double y1=p1.y-p0.y;
    double y2=p2.y-p0.y;
    return x1*x2+y1*y2;
}

double angle(Tpoint p0,Tpoint p1,Tpoint p2){
    double cr=cross(p0,p1,p2);
    double dt=dot(p0,p1,p2);
    if(!dcmp(cr)) cr=0.0;
    if(!dcmp(dt)) dt=0.0;
    return atan2(cr,dt);
}

bool cmp(const Tpoint& a,const Tpoint &b){
    return dcmp(atan2(a.y-p[0].y,a.x-p[0].x)-atan2(b.y-p[0].y,b.x-p[0].x))<0;
}

bool cmp2(const int &a,const int &b){
    return dcmp(angle(p[a],p[0],p[1])-angle(p[b],p[0],p[1]))<0;
}

void init(){
    Tpoint tp;
    int i,j;
    double minx,miny;
    cin>>n;
    for(i=0;i<n;i++) cin>>p[i].x>>p[i].y;
    for(minx=miny=inf,i=0;i<n;i++)
    if(dcmp(p[i].x-minx)<0 || (dcmp(p[i].x-minx)==0 && dcmp(p[i].y-miny)<0)){
        minx=p[i].x;
        miny=p[i].y;
        j=i;
    }
    tp=p[j];
    p[j]=p[0];
    p[0]=tp;
    sort(p+1,p+n,cmp);
}

void solve(){
    int i;
    for(i=0;i<n;i++) id[i]=i;
    sort(id+2,id+n,cmp2);
    cout<<p[0].x<<" "<<p[0].y<<endl;
    cout<<p[1].x<<" "<<p[1].y<<endl;
    //for(i=2;i<n;i++) cout<<p[id[i]].x<<" "<<p[id[i]].y<<" "<<angle(p[id[i]],p[0],p[1])<<endl;
    cout<<p[id[n/2+1]].x<<" "<<p[id[n/2+1]].y<<endl;
}

int main(){
    init();
    solve();
    return 0;
}
Re: I got WA on test #7
Послано xiaomengxian 26 сен 2006 19:15
Me too....
BTW, are you from HNSDFZ?
Re: I got WA on test #7
Послано gojiajunchao 2 июн 2008 06:47
1e-8 => 1e-10 then you will AC