1.
http://local.wasp.uwa.edu.au/~pbourke/geometry/2circle/ uite aici al 2-lea rezultat de pe google e destul de bine explicat
2.
http://www.faqs.org/faqs/graphics/algorithms-faq/ Gasesti aici si explicatie la formula centroidului. Si aici o explicatie ceva mai buna zic eu la formula ariei
http://geometryalgorithms.com/Archive/algorithm_0101/3. Chestia cu pointerii ce fug unul dupa altul (cred ca la asta te referi cand zici de rotating calipers), e nasol de implementat sa scapi de cazuri simple in implementare. Cel putin pentru dreptunghiuri nu am reusit sa fac sa nu cicleze la infinit. Implementam asta acum 8 ani deci probabil acuma daca as implementa mi-ar iesi. Algoritmul respectiv e O(n + m) dar in concursuri nu cere nimeni asa ceva. Era un articol vechi in ginfo cu algoritmul asta
http://www.ginfo.ro/9_8/061.shtmlUn algoritm simplu ar fi sa implementezi intersectia de un semiplan cu un poligon convex. Poti face asta se face foarte simplu cu o lista dublu inlantuita. O intersectie dureaza O(n) is cum trebuie sa faci m intersectii algoritmul final va fi O(nm).
Alt algoritm ce il foloseam pana sa ajung la idea de intersectie de semiplan cu poligon convex era urmatorul:
- gasesti toate intersectiile intre laturile celor doua poligoane O(n * m)
- gasesti punctele dintr-un poligon ce sunt in interiorul celuilalt O(n * m) sau O(n log m + m log n)
- faci infasuratoarea convexa a punctelor rezultate din cei doi pasi mai sus O( (n + m) log (n + m) ) si asta e intersectia celor doua poligoane
asta e mai nasol ca trebuie sa implementezi pe langa intersectie de segmente si punct interior unui poligon si infasuratoare convexs
Cu exceptia cazurilor in care se specifica altfel, continutul site-ului infoarena